Have a few thoughts on the topic, but the general gist is if a user inputs a new password, is it possible to have a high confidence that a password is not being reused elsewhere? By elsewhere, I mean on any systems not controlled by you.
If the user is allowed to pick their own password, then no, it is not possible. Nothing prevents that user from re-using some other password from other systems you do not control as long as it fits all your password requirements.
If you do not allow a user to pick their own password, but generate a high-entropy password for them then it is possible -- if you pick a random new 80-bit password for them like
LDhrcqKYcm its highly unlikely that before generation that password is used on any other systems. Granted once you give it to the user, there's nothing preventing them from memorizing it and deciding to use it on some other system that doesn't put limits on their password.
From a technical perspective, I think it's clear the answer is "no" since you, presumably, don't know their passwords elsewhere, and, ideally, don't know their passwords once set on your system either.
I think there are easily conceived approaches to determining statistical likelihoods that someone is (or, as you said, isn't) reusing a password. For example, a poorly chosen or simple password like "123456" may be more likely to belong to someone who reuses passwords, while a password like "*lP(../#x9`" probably belongs to someone who doesn't.
In either case, however, I think it would be sufficiently difficult to determine with "high confidence" either way that it would probably be of more value to accept that most people reuse passwords, and to then implement password requirements that deincentivize reuse, or add multifactor authentication to mitigate against reuse.
Just my 2 cents.
The only thing that can be controlled well enough is the strength of password that a user can choose. By strength means making mandatory the usage of special characters, case-mixing etc. As Wizard said, two factor auth is a very apt approach because you can control the OTP part of it and allow the user to choose any password he/she wishes.