Should secure passwords be tested to be unique?

Many services force you to use long passwords that don't closely match a text book etc. If a service knows my e-mail address, wouldn't it make sense to test if the password is the same for the e-mail provider and refuse to accept a recycled password? The spotify incident suggests this would be a very acceptable behavior but I would really hesitate to even test a password on another system when the only thing I did was to refuse that password and suggest to also change the now compromised password at the other service.