You start typing the address and when it pops up, highlight it and hit the delete key. That will remove just that one cached address from the NK2 file.
edit since this grew longer than a comment response
I'm not sure how worth it it would be to find a utility that would manage 500 users' NK2 files individually and do this yourself to clear out only SOME old addresses. If it were me, I would make everyone aware of what is going on and why their mail may get bounced sending to some users and how they themselves could clear out their own cache address by address if they have this problem. You may have to hold the hand of less-knowledgeable users yourself, but you will avoid potentially corrupting NK2 files using a utilty behind the scenes. You could always just wipe out their NK2 files altogether as well, but again you should let users know beforehand so you don't get tickets asking why names no longer pop up.