already wrote about this two weeks ago.
the client wil handle it this way:
1. check if address is within own address book -> green
2. if account exist within blockchain -> yellow
3. don't exist within blockchain -> red
simple visual control.
Why invent crazy schemes when there is a simple, elegant solution, which covers both client AND server - checksums. The way it's implemented in bitcoin.
I don't buy the whole "oh my god performance" line of reasoning. You wrote it in Java, for god's sake

as soon the extra bit's are available for this, i can add it.
just to explain why a colored feedback is not only eyecandy but usefull, consider this.
the first step is to enter the address where to send the funds. when done the address
field is loosing focus because you do the next step, enter the amount. at this point you
get the visual feedback already about the account number. no need to fill out all other
fields and press send to know something is wrong with your address.
just a little thing but userfriendly and i can add it right now.
as said, just an example...