depending on how many addresses you need to validate,(and you want to do it yourself) this link below could be an option;

i'ved used this to clean up and validate a non profits contact list of a few thousand names:

it's a CLR that you'd have to add to a 2005+ instance, which in turn has linked servers to your 2000 database;

so the data can stay on 2000, but the cleanup requires CLR, so that's 2005 at a minimum:

http://yaddressudf.codeplex.com/

as i remember it, once you hit 2000 addresses, it starts stops processing and asks you to buy into theri service, but even then it wasn't expensive(well, more expensive than free, but still)

i've got a bookmark somewhere where there is a free service from some education institution, but i never bothered making a CLR to hit that service; if you still need a free solution, i'll try to find that web service for you .