Dan,
not normally one to put my sales hat on in this environment, but I am actually a database marketing consultant, and something that strikes me as a little odd is that the address cleanse is only carried out when the data is required.
Are there steps which you could take to improve the quality of data on entry, thereby avoiding this occasional problem.
It does seem like an inordinate anount of work to try and do when deadlines loom (ie. mailings need to go out).
If you were able to send me a sample of the data, I will see if I can come up with a routine for you (gratis) but I really would emphasise the benefits of getting the data right on entry, because any routine you were to produce will undoubtedly come up with more than a few "Manual check required" flags.
Regards
Phil.