What is the possibilty of someone who is deported for having entered into the US illegaly to become legal?

It does not look good. He might be barred for another 10 years if he was re-deported. This might only be waived with a waiver that can accompany a non-immigrant visa but there is little likelihood of approval of that given the facts.

Under current Regulations, the subsequent Removal prior to remaining outside the US for the 10-year penalty period following his initial deportation may subject him to a lifetime ban. Barring substantive changes in the Regulations as they currently exist, his possibilities are remote at best. You should contact an experienced immigration attorney who specializes in Removal work.

Your husband has made an awful mess of the situation. Appears to me that he is now subject to what is commonly referred to as the "permanent bar" described at ?212(a)(9)(C) of the Immigration and Nationality Act. What does this mean? A foreign national who has accrued a period of one year or more of "unlawful presence" in the US will be barred for ten years from returning. There is a "waiver" available to get around this problem if the foreign national can establish that it would be an "extreme hardship" to his spouse or parent (who is a resident or citizen) if he is not permitted to return. However, if that same person then attempts to come to the US illegally the foreign national is now barred for ten years and cannot file a request to have that bar "waived" until he has remained outside of the US for ten years. So the first bar permits the foreign national to apply to have the bar waived at any time before the expiration of the ten year penalty. The second bar requires that the individual reside outside of the US for ten years before being able to file the waiver application to return. There are few penalties under US immigration law which are much worse or much harsher than this one. The purpose here is to deter people from frequent violations of the immigration laws and the conduct n which your husband engaged is impossible to fix without waiting an extended period of time to fix it. I completely understand the difficulties which are apparent when situations such as these create separated families. But we are a nation of laws and a nation with a border. When those laws are violated and the border not respected, the penalties which can be imposed are very harsh. Be careful out there, attorneys and others will tell you that they can help when they can't. I encourage you to seek the advice of a competent and knowledgeable attorney. Just make sure that you are dealing with someone who is licensed and someone who has the qualifications to provide you the advice that you need. Good luck.