milimelo

You were misinformed at USCIS - btw, you do not file a petition with e local office, you read the instructions and send it to Chicago Lockbox.
You have no basis for adjustment of status as spouse is LPR. File ONLY I-130 and in the meantime stay in student status until the visa number is available. Follow priority dates on visa bulletin (state.gov) and when your number is current you can file I-485 with a copy of your I-130 notice.

I would just tell them.

Her case isn't that complicated. She was here on a CR-1 and left before having conditions removed and somewhere in the process got divorced. Unless there was a VAWA case initiated then the CR-1 is done and over with. There is no basis for returning to the US on that as she no longer has a USC husband. Student or tourist visa is pretty much a guaranteed rejection as via the CR-1 she has shown an intent to immigrate. The only real option is a H1-B visa sponsored by her current employer.

Pax, questionable if she overstayed the tourist visa, kinda thinking she did, but the green card expired March 2009 and she didn't leave the US until summer 2010.

Sounds like your green card was expired prior to you leaving the US yes? If so there is no way you can obtain a returning resident visa as you had to be a resident when you left to qualify.
Permanent resident aliens who are unable to return to the United States within the travel validity period of the Alien Registration Receipt Card, or the Reentry Permit, may apply to the nearest U.S. consular office for a special immigrant Returning Resident (SB-1) visa. To qualify for such status aliens must show:
That they were lawful permanent residents when they departed the United States;
That when they departed they intended to return to the United States and have maintained this intent;
That they are returning from a temporary visit abroad and, if the stay was protracted, that it was caused by reasons beyond their control and for which they were not responsible; and
That they are eligible for the immigrant visa in all other respects.
Source.

They like to see the birth certificate, but if you can't find it it's not going to be a deal breaker as the US passport is indeed proof of US citizenship and proof that your husband was born in the U.S.of A.

Any time spent in the country other than your own home country does not count towards the 2-yr HRR.

If you file to naturalize then they will be force to adjudicate the ROC.

Ebbas is mixing things up.
I would say is you are helping someone to illegal enter the country by showing the finance.
As you have mentioned your friend is asking you to show your finance documents to bring her niece over but then who is going to pay for her education if your friend cannot pay and her niece cannot pay then who is going to pay?
She will dissolve into thousands and thousands of illegal immigrant, if I was in your place I would not do it.
By helping her you are only helping illegal immigration.

Jose Antonio Vargas: Poster child for why E-Verify must be mandatory
Washington Post’s illegal alien stole a job from an American
By Dan Stein
The Washington Times
9:02 p.m., Monday, July 4, 2011
Jose Antonio Vargas, a former Washington Post reporter, has come out of the closet and announced to the world that he is an illegal alien. In his tell-all confession, published in the New York Times Magazine, he outs not only himself, but others who abetted his illegal presence and employment in the United States, including The Post itself, which continued to employ him even after a member of the paper’s management learned that he had lied about his citizenship.
Most important, Mr. Vargas‘ confession exposes the ease with which he, and millions of illegal aliens like him, can circumvent the law. It was as easy as a piece of white masking tape and a photocopy machine. Mr. Vargas writes that when he was a teenager, he and his grandfather covered over the portion of his Social Security card that said he was ineligible to work in the United States before photocopying it. Using a copy of an already flimsy card that constitutes the most important piece of identification Americans possess, Mr. Vargas was able repeatedly to flout the law against illegal aliens working in this country.
If any of his employers - The Washington Post, Seattle Times, San Francisco Chronicle, Huffington Post - had simply verified his Social Security number, they would have learned that it was invalid for employment. If the Social Security Administration (SSA) had been required to disclose that it was collecting taxes on an account that was not authorized for employment, the government itself could have identified Mr. Vargas as an illegal alien and taken action. But employers are not required to verify Social Security numbers, and government agencies are not required to inform other government agencies that laws are being violated. And so we have an estimated 7 million illegal aliens on payrolls in the United States.
Whether it was his intent or not, the timing of Mr. Vargas‘ confession provides compelling testimony in support of legislation introduced earlier this month by House Judiciary Committee Chairman Lamar Smith (Texas Republican) and the ranking minority member of the Senate Judiciary Committee, Sen. Chuck Grassley (Iowa Republican). Both of these bills would mandate that instead of a cursory inspection of any of more than two dozen different documents, all employers would be required to use the E-Verify system, which verifies information against Social Security and immigration records.
The Smith and Grassley bills also would discourage an additional and common form of fraud perpetrated by Mr. Vargas. In his public confession, Mr. Vargas admits to having perjured himself repeatedly by attesting that he was a U.S. citizen on the I-9 forms he filled out for employers. Mandatory verification of his Social Security number would have revealed that he was neither a citizen nor an alien authorized to work in this country and could have subjected him to criminal charges.
The common practice of using someone else’s valid Social Security number to gain employment would become more difficult and riskier under both the House and Senate bills. The bills require SSA to flag numbers being used by more than one worker, in much the same way that credit card companies routinely freeze accounts when they suspect fraud. Enhanced civil and criminal penalties, including mandatory prison sentences, against illegal aliens or employers who engage in identity theft or fraud would be an additional deterrent to this sort of abuse. To prevent this sort of fraud from occurring, greater cooperation and information-sharing between government agencies would be required.
As Mr. Vargas‘ story illustrates, employment of illegal aliens is not limited to shady businesses on the fringes of the American economy. Even companies whose integrity is their stock in trade are affected. A system that depends on employers examining documents they have no way of knowing are valid or allowing people who are intent on breaking the law to check a box attesting that they are citizens makes a mockery of the law.
E-Verify is a proven secure and reliable system for denying jobs to illegal workers. For those who still may harbor doubts that universal employment verification is necessary, Jose Antonio Vargas is Exhibit A.
Dan Stein is president of the Federation for American Immigration Reform.
http://www.washingtontimes.com/news/2011/jul/4/jose-antonio-vargas-poster-child-for-why-e-verify-/

Pardon? Unless he's a personal friend of President Obama then the chances are pretty much zero.
Entering illegally removes 95% of the possible options for acquiring legal status in the US. If any of those "fake documents" made it appear he was a US citizen then he's doomed. There is no option for him to get legal status in the US. It is one of the worst possible immigration violations, and results in a lifetime ban.
One possibility is cancellation of removal. It's very tough to get. He'll need to prove he's been continuously present in the US for at least 10 years, that he's been a person of good moral character, that he's not subject to an inadmissibility bar for any criminal violation, and that he's got qualifying relatives (spouse, parent, or child) who are either US citizens or LPR's, and who will suffer extreme hardship if he's deported.
If he's married to a US citizen or LPR, and suffered abuse by his spouse since arriving in the US, then he might be able to get a green card through VAWA.
The only other option I can think of is asylum, but that's not going to happen if he's from central or south America.
If you consider attempting any of the above options then you should seriously consider hiring a very good immigration attorney. It will cost a truckload of money, and your chances of losing are high, but your chances of success without a good attorney are practically non-existent.

Here's the deal. Someone who is married to a US citizen and suffers abuse from their spouse while in the US can file for adjustment of status based on a VAWA petition. It is possible to file the petition while the alien spouse is outside the US. So far, so good. The bad news is that you must either still be married to the abusive spouse when you file, or if divorced then it must have been less than two years since you divorced and you must prove that the abuse was a primary factor in the divorce. You must also not have remarried before the VAWA petition was filed.
Based on what you've said, I don't think you have any basis to gain permanent resident status in the US based on your prior marriage.

You cannot restart where you left off. That green card eligibility ended when you left the US 5 years ago. Even if the GC was issued it would only have had a 2 year duration at which point you would have had file for removal of conditions. That time passed a few years ago.
Sorry to say, but you have no claim to residency at this point.

If they don't intend to be living in the USA its kind of silly to renew/apply for a new green card, its not a visitor pass to the USA. The green card is for LIVING in the USA.
The green card status becomes abandoned after not living in the USA for a year. I'm pretty sure their GC status was canceled before the card expired.
If they want to visit they should apply for a visitor visa.
If they want to live in the USA they will have to be sponsored and start all over again with the paperwork and fees and wait till approvals etc.

What is Hold Departure Order? Does this mean the Philipines government stopped you from leaving their country for the last 6 years and if so why?
You most likely will not be let into the USA, as you'll be considered to have abandoned residency with such a long absence. You will need to be petitioned again, via a I-130 as you say. It will not be any faster because you were an lpr previously. How long it takes will depend on who petitions for you.

Important: Show up anyway at the original time on the original day, with your original appointment letter in hand.
If they won't let you in, you can say that you never got a letter to the contrary.
If they do let you in, you're where you were to begin with.
If the history of other VJ members is to be believed, it can be folly to believe these "cancellation" letters.

Do an immediate debriefing with your husband. Ask him to write down every question he can remember and every answer he gave--this is not the time to be defensive, but rather to put yourself in the place of the CO and see how you would have reacted to his answers. Also, what other red flags are there with your case--a few bad answers usually aren't enough to derail a case. Be brutally honest with yourself--and do it immediately while everything is fresh in his mind.
Then come back and tell us all the red flags as well as the questions and his answers, and then we can start to help.

Visiting the US and living in the US are worlds apart.

Well she can either wait for ROC and change her GC then, OR she can pay the $455 fee to file the I-90 to replace the greencard with the married name.
She shouldn't change anything until her GC is changed. When working she works in her GC name, which means she'll file taxes in that name, but it needs to match her SSN. And you can't change the drivers licence until she changes the SSN.
It's just simpler to do the GC first THEN do the rest. She can of course call herself by your last name, but any legal forms she is maiden name, until she changes the GC.

May be time to get your spouse's representative involved as it has been over 6 months and no AOS GC.

I have read here stories where people got a 10 year card by mistake and then were deported in absentia when they failed to remove conditions after 2 years.
OP - If you are approved on your interview date, you will get a 2-year card which is good for 2 years after your interview date. Yes, you will file for removal of conditions when you are nearing your 4th wedding anniversary.

That penny's worth of advice applies not only to what you should have done, but also to what you still should do. Forget everything that's gone wrong up until now. Go back to square one, get it right, and start the process from the beginning. Yes, the process is complicated, but it's not so complicated that you need an attorney. Anyone with average intelligence and a willingness to learn can handle a routine case on their own, and your case seems pretty routine.
Now, if you'll permit, I'll add a few comments to your bullet list...
(a) conduct the marriage in the country you intend to take residence permission.
Not always possible. Getting married in the US is a snap in most states. Getting into the US in order to marry here is considerably more difficult. You've spent some time in East and Southeast Asia, so you probably know that getting a visitor's visa in some of those countries borders on the impossible.
The percentage odds of my wife or any of her family getting a visa to visit the US could be counted on the hands of Three Finger Jack. On the other hand, getting married in her country is a bureaucratic nightmare which includes an interview by the VN government wherein she has to prove she's proficient in MY language by translating questions and responses in front of two professional translators. Even with her current level of "Vinglish" proficiency, which I understand completely, she couldn't pass that test today. For us, the only practical option was a K1, which also came with the added bonus that her older teenage kids would be eligible for K2 visas, while they wouldn't have been eligible for CR2's. How did I learn this stuff? Basic research.
(b) expect confusion between the two different country agency when explaining your condition.
I'll take this a step further. NEVER ask a low-level government bureaucrat for help with a complicated bureaucratic process. The first line of "defense" that any agency of any government puts up between them and the citizens they serve are low-paid uneducated dolts who would only intentionally help you if they did it accidentally. If they actually knew anything about laws and policies then they'd have a better job deeper in the bureaucratic machine, and farther from the customers. Do your own research. Most lawyers are no smarter than you, and you are equally capable of understanding laws and policies. In the 21st century you also have a wealth of educated people on the internet you can turn to for help. Proceed only when you're sure that YOU understand what to do.
(c ) remembering Governments are not logical, the systems are made complicated, and if someone tells you otherwise they are full of fluff. ( But rummer has it that Immigration Reform is on the way. . . just don't hold your breath.
For every seemingly pointless bureaucratic hurdle they throw in your way, there is a valid and sensible reason if you dig deep enough. Let's look at the marriage certificate thing as an example...
Immigration fraud has always been a big problem in the US, and probably always will be. This is understandable, given that the US is the biggest immigration magnet in the world, beating the #2 country by a factor of six. Bear in mind that this is based on a perception of the US that doesn't really jive with reality, and there are other countries where the standard of living is actually much better (Switzerland, for example). Nevertheless, more people have a desire to immigrate to the US than anywhere else.
Many people's eligibility to immigrate is based on family relationships with US citizens and LPR's. The proof of their eligibility often hinges on foreign documents like birth and marriage certificates. Before there was a standardized method for verifying these documents, US immigration authorities were frequently defrauded by aliens presenting forged or otherwise fraudulent documents. Congress decided that the responsibility for establishing uniform standards would fall on the Department of State, since they are the only government agency with an official presence in each of these foreign countries through the US embassies and consulates. The end result was a collection of standards called the "Fee and Reciprocity Tables", which details for each country whether a particular type of document is available, who it's available from, and what exactly a document should have in order for it to be considered valid. For all US government agencies that have to deal with foreign documents, the reciprocity tables are the "bible" they rely on.
An inference you may freely draw from the above is that the average US immigration officer wouldn't have a clue if a document were valid without the reciprocity tables, as well as visual examples of valid documents. You could have a perfectly valid document which would be accepted by a foreign government without question, but if it doesn't exactly conform to the reciprocity tables then the US government won't accept it. Armed in advance with this knowledge, you know what you need to get in order to satisfy them.
As far as immigration reform, as you say, don't hold your breath. I don't think it will be coming soon. If it does, it won't make immigration easier. In any country with a weak economy, the public mood will always be anti-immigration. Most Americans don't want to see immigration made easier, and they want much stronger enforcement of illegal immigration laws.

You are limiting your options to what is convenient for you. Appealing the fiance visa process may not even be an option. Usually they just notifiy you the petition approval has expired and you can try again if you wish. Even on appeal, the same issues will be there. The strongest evidence of a bona fide relationship is time spent together in person. In your situation, my opinion is that you'll be wasting your time trying anything until you can spend some significant time together as a married couple. Consular officers don't care one bit about the inconvenience to you. Bona fide relationships with foreigners are seldom convenient. Everybody here knows that first hand.

Many states (maybe most) have mandatory arrest laws for domestic violence. If someone calls the police and claims they were abused, and the police see any evidence of physical abuse - scratches, bruises, etc., then they are compelled to make an arrest. If she is ever alone with him then he can smack himself around and call the police and blame it on her. If he knows she's alone, even if she's not with him, then he can do the same and she won't have an alibi. This is a serious risk, and if he's getting guidance from people who understand the law then they'll be able to tell him how to pull it off. There are web sites that specifically instruct immigrants how to do this.
She needs to lawyer up, and she needs to make sure she's never alone.

Its sponsoring a foreign national that compromises it.
It does cause problems even for military people. They have to retest and take frequent testing/polygraphs to prove they are not giving info to this foreign national etc.