Did you ever figure your situation out? I am having the same exact issue! I feel backed into a corner and hopeless!
Private loans are a completly different animal from federal loans.
The reason the DoE couldn't find the OP's private loan is because they have no jurisdiction over a private loan, and you cannot consolidate a private loan into a federal consolidation loan. Some private lenders will allow you to consolidate federal loans into a private loan, but you almost never want to do that.
Private loans do not have the same protections and benefits that federal loans have. Private lenders are not required to offer you payment plans like IBR and PAYE, they do not have to offer rehabilitation, they don't even have to consolidate your loan unless you meet their credit standards.
My reccomendation would be to investigate the statute of limitations in your state and the state where you took out the loan to see what laws apply to this debt and when it might be out of SoL. Once you're out, they cannot sue and garnish you. Until then, they can sue and seek action like garnishment. Actions you take, like making a payment, can reset the SoL in some states/situations.
The Rebuilding Your Credit forums here will have good info for you. In the case of default, private student loans behave much more like other unsecured debt (like a personal loan or credit card debt) than a federal student loan.
EDIT: Just saw the date on the OP properly, doubt they are still around. You may want to start your own thread with your own details rather than continuing to post in this one since it is so out of date.