Your question is a good one. Some well known members gave their answers in this thread.
My view: Directories and IYPs get crawled and rank. The only difference is that their geo-vertical target pages contain content that is local by nature (natural). So your challenge is to do, or appear the same.
The key would be to create a page/city site map directory structure thats linked to/contained in home/root - one that is not easily identifyable by the user. The page should read something like "We specialize in service in the following cities" Beyond a link, write a unique sentence or two for each- a special condition or unique client in each city for example. Start small, build you city list up as indexing and ranking shows positive signs, and be as natural as you can on each page.
The challenge is as much a user perception challenge as it is a ranking challenge. I think in the end the user and the engine will want to see the same thing - unique content geared specifically to that geo + service seeking user.
Try a unique city picture on each page. Maybe consider showcasing clients from each city on each unique page. Even consider geo specific outbound links. Make sure the first third of the page is unique. Get unique city based links that point to geo-service pages.