I contacted support and they informed me that they are unable to trace the recipient of my BTC as I failed to generate a receiving address via their site(which I thought would stay the same after it was generated last year). It seems all hope is gone...
I find it a little hard to believe that they just "deleted the private key" (surely they take and keep monthly backups).
I'd keep an eye on the address to make sure that the funds don't move (if they do then the exchange has lied and stolen your BTC).
Gotta agree with CIYAM on this one. My gut feeling is that either:
a.) They are outright lying to you
or
b.) BTC has already been spent and they are outright lying to you.
I don't know of any reputable exchanges that don't keep regular backups of their entire system. Definitely watch that BTC addy, (FYI, there are services available that will e-mail you of any balance changes such as
http://bitnotify.com/)
This way you don't have to constantly check blockchain.info by hand to determine whether or not anything has happened to that addy.