Ajax might be a solution. I've done something similar for validating email/postal address "on the fly", but it's been so long ago...

Check the old dbman flat file Mods, I have something from 2006 where someone used it as an example to check if a user name was "already taken" before the person clicked the "sign up button". Don't know who wrote it, or where it came from, but it might point you in the right direction.

I will keep poking around and see if I can find that chunk of code as well.