Dear Friend
Did you approach the company in person which was not given you relieving letter? why because in some companies, HR dept staff are ignorant to address the problems of ex-employees who will make a call and request to resolve their grievances if any. Hence, it is always advisable to go in person and request concerned HR to issue a reliving letter by informing him that you got a chance to serve in MNC and if they do not give it, you will loose an opportunity. Generally, every HR might consider this type of request and certainly, they will give your relieving letter.
If HR dept is not giving said letter in spite of making requests repeatedly for one or the other reason, then meet unit head and tell him about your offer with MNC and response of HR dept in your case. If he is good definitely, we will asks HR to issue a letter to you to that effect.
Even this unit head also not interested to issue the same, you should have to think that they are having some thing in their mind about your attitude / performance and in such a case, you need not stress for it. Simply, you can inform your new employer by telling the facts about your employment with said company and request him to give an exemption for submitting relieving letter from such organisation.
Regards