Yo muj* America ma je gare pani bhayena!! Afnai hard work le graduate bhayo, afnai effort le full time jagir pani payo ani aile bhuttro jasto H1B gardaina po bhancha ani E-verified pani chaina re!!

For a company to get e-verified its less than an hour work. They just have to provide some information and answer some questionnaire  that is listed in the e verification registration page. I requested my boss and they e-verified their company the next morning. It only depends on whether your company wants to be e-verified or not.  

My employer did not know anything about e-verification. After i explained he asked me to send the link to register then he registered in less than an hour.

Ohh Bro, don't get tensed man. Its better to work for one and a half yrs more, than to get unemployed. As mentioned by other fellows, its easy to get your company to e-varify. Explain that to your supervisor and then start looking for jobs outside while working there as well. Best of Luck.

in OPT you can alwasy work for multiple employer. Everification is only required to renew your OPT. So my suggestion is to work in same company and search for some Consultancy and register yourself so that you can use their name while renewing the OPT. If renew process requires pay cheques, the you can pay tax to those consultancies and they will generate the payroll for you. This is just a work around in the worst case. Good Luck.

Thank you so much for your suggestions. From the conversation that I had with the HR yesterday, they're at least willing to participate in the E-verification process if it's "simple" and "less expensive". By the looks of it, it doesn't seem all that complicated and on top of that, it's free. So, hopefully something works out without having to go through consulting companies. Thanks everyone.