Hello Suresh,
Going by the terms of employment you mentioned, it's clear that you don't have a Buyout option.
Did you inform 'in-writing' that you are joining the Govt sector & NOT another Company?
Despite all the various advantages in MNCs, the one disadvantage is about the Rules being more like in a Govt--rigid & without flexibility when left to the bottom-rung guys.
Like Nathrao suggested, the only option for you is to escalate to the Top--WITH a copy of the Govt Offer letter.
DON'T......repeat DON'T......harp on your side of the story about getting relieved earlier. Focus & sell the fact that the Company won't be effected in any way by your leaving now or later.....since you WON'T be joining another Company.
Focus on the usual human tendency/frailty about acting only when things effect oneself. Since your manager has given you the Clearance, you have a lesser headache.
The Worst-case-Scenario action would be what Venu suggested [he is right that Govt sector doesn't insist on earlier job Docs, UNLESS there's some criminality/legal issue involved].......joining even if you don't get the Docs here.
But I wouldn't suggest it as the direct step without trying your best to get the Docs.......for all you know, you may want to quit the Govt job later & join a Pvt sector Company. That's when your lack of connecting career Docs will effect your chances very badly.
MAYBE, you can use this fact in your discussions/mails to the Top guys [don't see any point to mention it to the junior HR guys....they wouldn't understand the sanctity you are attaching to getting out the proper way]......"that you CAN leave even without any Docs but DON'T WANT TO as you value your association with the Company".
It will only enhance your chances of getting relieved faster & properly.
All the Best.
Rgds,
TS