Tax records showing your employment, there is also the option to have your personal referee vouch for the gaps. As for a recalcitrant employer withholding notice of employment, I believe there is no law against this, you can however by use of your personal referee's claim that due to a dispute they are not supplying a reference..along with tax records and/or the referee's letter.
I would also say its worth speaking to the ID centre and explain your situation to them.
If its a BAA airport your airline should have a specific account manger that deals with these issues.
Hope this helps
