I'm not following. You have a full legit copy of windows 7 ultimate (a first I must say...) which MS agrees is good. But you don't have the lower copy of windows? That's what MS is upset about? But then you also write;
Installing a new full version of Windows XP from E-bay on a 64 bit machine, before re-installing an upgrade version of Windows 7 Ultimate.
There is no way to upgrade XP to win7. Or rather there is no in place upgrade. Research how to do the "double install" method of Win7 and it should fix your problem assuming you have a real legit copy of win7.