Hi Donnie,
I'm very sorry to read that an SEO company suggested forbidden tactics. That burns my onion, and, as you can see, you were guided into a situation that has ended in really negative outcomes for your business. So, it's definitely time to turn your back on anything spammy you learned from this SEO firm.
Unfortunately, as your business has already been punished for violations, there is nothing you can really do at this point to get back into Google's good graces apart from vowing to play by the rules from here on out. Memorize the rules and check back from time to time to see if they change:
http://support.google.com/places/bin/answer.py?hl=en&answer=107528
I truly do understand the frustration - I've spoken with so many business owners who are just on the borders of major areas in which they wish to rank or in which they serve - but the answer is the same for one and all: if you want to benefit from the exposure Google's products offer, you must play by their rules.
How you and I may think Local should work is, unfortunately, totally beside the point. It is Google's conception of how their products should work that matters. You need to try to understand their vision and see how you can fit into their vision, rather than trying to bend that vision to fit your individual business.
So, how Google feels right now (and they are constantly changing their policies) is that a business is most relevant to its city of location. If you're physically located in city A, you can make your best effort to gain high blended/local rankings with a clean listing, citation building, content development, etc., in City A. You cannot reasonably set the same goal for Cities B, C, or D, because you're not physically located there. There are exceptions to this, but they have been rare since the Venice update in early 2011.
Your best strategy for gaining some visibility for these other cities where you're not located will have to be to make efforts that gain secondary organic visibility...not primary local visibility. So, certainly, have a Places Listing/Google+Local page for your true location and authentically represent your business locale everywhere your data is published on the web, but don't engage in any work that paints a false picture of your business. Your customers do not want this, Google does not want this, and as you have seen, they are cracking down harder and harder on their definition of spam.
It is my understanding that records exist of edits that have been made to accounts...if that is correct, then you've got to see your profile as being marked with a big red flag that any Google editor can see. That being the case, I strongly suggest that you do not try to get back into finding workarounds (such as forbidden virtual offices etc.). If you were my incoming client and had come to me with this issue, I'd be preaching the straight-and-narrow sermon to you and telling you that you've got to forget anything spammy you learned from the old SEO firm and start adhering to all guidelines to the letter. I don't want to go on and on about this, but I do feel real concern about whatever else that bad SEO firm may have taught you about Local.
I have read of cases in which, in order to get more visibility out of the system, businesses with suburb or metropolitan border issues like yours have decided to move their companies to new offices, and while that would certainly be a legitimate thing to do, it's also a rather extreme and expensive reaction. I have also read of cases of people moving offices within a city to get closer to the centroid or business cluster. Again, that seems rather extreme to me, but some people are apparently motivated enough to do so because of the large effect Google's products have on their bottom line.
So, what can you do? I don't know what your business model is (are you a stationary business like an attorney or a go-to-client business like a plumber?) but the tactics are typically the same:
-
Put the majority of your effort into gaining high local visibility for your true physical location.
-
Build citations to support your physical locale
-
Create a content strategy for featuring your work/involvement in other cities with the goal of achieving some secondary organic visibility for those keywords
-
Win/build links to support that organic content
-
If you can't get where you want to with either of these 2 efforts, you will have to engage in PPC to get the placement you want.
Something that might be helpful to think of in future: imagine that if instead of investing in the bad SEO company's spamming Google Places/+, you had put that money into content development. Imagine if that content had been so awesome, so shared, so linked to and cited that it was now supporting some visibility for you in those non-location cities. Right now, you would be sitting pretty rather than dealing with a big mess and loss of funds. You can start working on achieving this right now, Donnie, in hopes that it will serve you well in the future. Every local business can make this kind of effort, either in-house, or by hiring experts who are committed to using only allowed practices for the benefit of their clients. I'm rooting for you in turning this bad situation into a really good one in 2013!