I'd try an iterative apporach:

• Skim through the list and develop a number of basic regexes to match the adresses. Keep them rather strict and make your code fail (or output the non-matching records) if a record doesn't match any of them.
• Run it, then skim through the list of non-matching records and add more special cases to your rules (again, keep the rules rather strict)

• Go back to previous step until you have reached acceptable accuracy :)

I found this approach to be quite helpful in ensuring that I don't misunderstand records -- ie., thinking your rules match where in reality it is just pure chance and they're producing garbage without you noticing.