SEO for Trademarked Terms

A client has asked me for a strategy to optimize his website for trademarked terms that he cannot have show up on his website anywhere. Essentially, he is restricted from doing business outside of his service area, but he wants to get web traffic from these other areas.

The only method I can think of to do this is to do a crap ton of link building making the anchor text target these terms, but I'm wondering if anyone else here has any other ideas..?

At the bottom you could put "we don't service XXXXX city" to get the keyword on the page.

Yes, just build a bunch of links, and the above is a very good idea.
Put it in a H1, and maybe even title.

I'd throw up websites that are optimized for these terms and feed the visitors in from there. Just hit them with a pop-in with a big fat link 6 seconds after they hit the site. Bonus points if the 'close' button on the pop-in is not functional.