After a little more testing, I found that if I set the option "Match with no zones" to true, my match rate goes from 13% to over 80%. I am not sure why this matters since I am not using the city, state, or zip code in any of the addresses but it made a huge difference. The addresses left unmatched were actual problem addresses.
There was talk some time ago about changing the default value to 'TRUE' so you wouldn't need to. I can't remember reason it didn't materialize. Even though you don't use zones in your matching data, the locator 'looks for them and responds accordingly: It wants 1234 S Main St SomeCity, SomeState, SomeZip and when it can't find all that it dings you if you just have 1234 S Main St.