Physical Address Format
^[\d]+ [\w\.,\- ]+([\d]{5}(-[\d]{4})?)( .+)?$
Mailing Address Format
^[\w\.,\- ]+(\d{5}(-\d{4})?)( .+)?$
PO Box Format (used to exclude PO Boxes, taken from http://forums.asp.net/t/1551081.aspx?regular+expression+for+P+O+Box+validation
[P|p]*(OST|ost)*\.*\s*[O|o|0]*(ffice|FFICE)*\.*\s*[B|b][O|o|0][X|x]
NOTE: Since I'm using \w, underscores will get through this filter. I didn't think it was a big deal, but if you need to exclude underscores, it's easy to fix. The post office would apparently remove underscores if detected, as it does with all special characters other than hyphens between meaningful numbers.
I also didn't validate state, as we're feeding state through a dropdown. Regex validation would need to include every state and territory permutation (CA, Calif, California, etc...).
The last bit allows any character to be used after the zip code.
To see how the Post Office parses addresses, you can look here...
http://pe.usps.gov/cpim/ftp/pubs/Pub28/pub28.pdf