I really don't get it.
They have disabled a totally legitimate console from connecting to live, and have locked your save games to that one console, forcing you to start entirely from scratch.
Yet, there is seemingly no way of recourse? There is no way to speak to someone useful from Microsoft about access to Live? Someone from the UK rather than the usual americans and indians?
It all just sounds crazy! If what your saying is totally genuine, then they must have a pretty good reason for banning your console, as I'd imagine they only ban consoles they are 99.9% sure have been tampered with.
So it's £159+ to carry on your Xbox 360 'career'?
You could always take your story to one of the online blogs or something, see how big you can stir it up, they may perhaps change their mind then!