kaled - 6:21 pm on Jan 23, 2011 (gmt 0)
Since no one else has answered, I will chip in...
You need to collect together the facts and documentation, summarise it clearly and concisely with scanned copies of documents (such as payment records) but with account details at least partly obscured as appropriate for privacy.
You need to write a letter to go with the summary that states clearly that a mistake has been made by the registrar.
After this, you must use your own judgement, I would probably send it to the registrar by email and by registered/recorded post and possibly send a copy to ICANN. Set the email priority to "highest" and, if you do use snail mail, mark the envelope URGENT.
Also state that since the mistake is theirs, reimbursement of costs will be required and that these costs will be substantial if legal action is needed to remedy the situation.