Hi Doug,
You are quite correct that Service Area Businesses (SABs) fall into their own category in many ways when it comes to local search. I'll try to provide some helpful tips here.
Tip #1 - The most important thing for SABs to understand is that Google is heavily biased toward physical location. SABs must have at least one physical location in order to seek inclusion in Google's local index. This can be a home address - that's just fine! But it cannot be a virtual address, P.O. box, etc. And it should not be shared by any other business.
Tip #2 - Because of Google's bias towards physical location, the SAB should set the goal of ranking well in the local pack of results for the city in which they are physically located, but not in the surrounding cities they may serve. There are some exceptions to this, as in the case of highly niche business models or in rural areas wherein one business is the only one or one of very few serving a number of towns. In such instances, you might see these businesses surfacing in the local pack of results for more than one town, but this is the exception rather than the rule.
Tip #3 - Once the business has set its goal of ranking well in the local pack of results for its city of location, there are a number of steps that can be taken. The most important is to build a really strong website with the main pages optimized for this city of location geo term. If possible, complete NAP (name, address, phone) should be included in the footer and on the contact page, preferably in Schema markup. Content should be strong and be optimized in a natural manner for the service + geo terms. You will follow this up by creating a Google+ Local page in which you will enter but hide the address to comply with Google's guidelines for SABs. Then, citations should be built in a variety of places that highlight the business.
If, for reasons of privacy, you need to hide the NAP, then you can build citations only on those directories which allow you enter but hide the address. See Phil Rozek's article on this: http://www.localvisibilitysystem.com/2013/04/22/private-local-citations-where-can-you-list-your-business-but-hide-your-address/ There is more you can do in this vein, such as earning reviews and links, video marketing, social outreach etc. All steps serve to build the authority of the business on the web.
Tip #4 - Do not put a list of cities served on the website in the manner you've observed. Google updated their webmaster guidelines in 2012 to specifically denounce this practice. They consider this keyword stuffing, and you can read about it here: https://support.google.com/webmasters/answer/66358?hl=en
Tip #5 - Next, the business owner will want to make every effort he can to rank well for all of his service cities. Remember, the goal here is not to get local pack rankings, because he typically won't. Instead, he can go after organic rankings by the process of creating city landing pages on his website for each city he serves. The article I've linked to describes all of the ins and outs of this. Basic rules: you must have unique, strong content on each page you create. No thin or duplicate content. The authority of these city landing pages can be built up via the usual methods (earning links, social outreach, video marketing, etc.). Your chances of outranking competitors who have physical locations in your service cities are very slim, but you can frequently earn some visibility organically and some is way better than none!
Tip #6 - You will not be building citations for your service cities, because you lack a physical location. But, you can create a content development plan via which you will be adding to the geo-specific content of your website on an on-going basis. A blog is a great way to do this, continuing to build content on your website that showcases your work in your non-physical-location service cities, as well as in your city of location.
Hope these tips set you on a good path!