Based on what you've written so far about your employer, it is not clear to me that you and your wife really did work without authorization. There are some obscure regulations that deal with companies that have been taken over, have changed name, etc. This is the first issue an experienced lawyer would need to settle. In the event that you were legal after all, you could pursue AOS.
Let's assume that you and your wife really did work without authorization. First, note that section 245(k) only applies to (some) employment-based AOS applicants, not to diversity visa applicants.
Also note that there is a technical difference between being "out of status" and being "unlawfully present". See, for instance, the following link:
http://www.uncg.edu/ipg/iss/out_status.html
You and your wife would appear to have been "out of status" for the time you worked without authorization, not "unlawfully present", so your wife would not be subject to the 3 year ban.
If you still have a valid H1B visa and a valid approved H1B petition, you could leave the US and reenter in H1B status. Once admitted, this would "erase" any period you were out of status prior to this admission. You would again be eligible for AOS.
If you have AP, you could pursue CP. In the event your application is referred to Washington, DC for "administrative processing" you could always return to the US to wait it out. We received our appointment letter in the US. We traveled to our home country to attend the interview and were told during the interview that my case would require further administrative processing. The consular officer said that we could travel back on our AP documents (he had seen the AP stamps in our passports). After seven months we were told that administrative processing had been completed, and we traveled again to our home country to submit our passports to the embassy. There was a further five week delay, which we decided to wait out in our home country, before we finally received our visas.
As for good lawyers, it is my experience that many of them are just "filers". That is, they are good at filling forms. Most cases are fairly straightforward, so that's just fine for the majority of cases. Once things get complicated, I've found that many just lack relevant knowledge. On more than one occasion, I've had to correct my employer's immigration attorneys... If I were in your situation, I would contact one of the following lawyers:
http://murthy.com/
http://shusterman.com/
They really appear to know the finer points of well-known regulations as well as many obscure regulations that most of us have never heard of. They can represent you regardless of which state you live in.
