Your bf has a very complicated case. These are the following issues he will need to deal with:
1.Criminal charges for re-entry after being deported.
2. Automatic removal since he has already been deported.
3. Any stay at the BIA or 9th Circuit Court of Appeal level that may help hi stay until all issues regarding his prior removal is resolved.
Your best bet is to contact an experienced immigration attorney. This will be a complex and expensive battle. Good Luck.
I do not know if an immigration attorney can do much, but you need to consult with one immediately. There is just a host of issues that you raise and all of them are serious. This does not seem like a matter for amateurs.
First you need to contact an immigration lawyer. They are the only ones who can assist you, unless other criminal charges are pending. It sounds like he has lived in the US for a while. See if he qualifies for some type of relief.
Seth Weinstein, Esq.
Practicing throughout Southern California
This reply should NOT be considered a legal opinion of your case / inquiry. At this time I do not have sufficient factual/legal documentation to give a complete answer to your question and there may be more to the issues you raised then I have set out in my brief reply.