If you really want to dig in and have budget, I can see a lifetime in researching each, every variation. As a common search engine visitor, I visit google.com and type in:
If I get too many results or they seem screwy then I go for:
And if I'm desperate, ready to toss in the white flag:
"keyphrase cityname state"
About the only time I use the state abbreviation is when I'm attempting to think sideways and maybe find out another option that placates search engines. The more I think about this I'm shying further away from state abbreviations unless there is ample budget.
I'm not at all saying this is right, but is a common search strategy, to start broad and narrow as necessary.
Regarding titles, if there is space available I will put the zip code as well, just as in the footer now that I understand better 'citations'.
You lost me with the "dynamic" bit. Be it joomla, drupal, wordpress, magento, zencart, etc you're give a field where you enter the page title, a second for meta description. Please explain how this dynamic thing works.
"unless you do what one of our competitors did and publish pages that target lots of variations on the same title and heading"
- I saw that earlier this week with a manufacturer's site that is apparently getting away with it. But with a large black/white bird rapping on the door.