You can't install XP on a comp that has/had Vista on it.
That is not quite correct (at least as far as clean installs go).
I have installed XP back on two computers (one desktop and one notebook) that has had Vista on it. I am referring to clean installs, not upgrades.
The XP set-up allows me to delete the partition it sees (a large one with Vista on it) and then adds the small unused (8 MB or so) to the unformatted partition that is left after deleting the partition formatting and information. I have done this with 'Vista Home Premium OEM' on the machines and then installing both XP Pro OEM and XP Home OEM (all were 32 bit).
The desktop has also had XP Pro OEM and XP Home OEM installed after having Vista Business Retail on it. It is currently back to running Vista Business, which I am posting from.
Perhaps there is something going on with 64 bit versions, but 32 bit versions are easily installed. I have performed 20+ of these procedures on both machines with no issues other than time spent.
One other alternative is to use a free disc partition utility like 'Seagate Disk Wizard Starter edition' to remove the current partitions and repartition the drive from boot. Once partitioned, you should be able to boot from the OEM XP installation disc and then format (or delete and format) to install XP.
Again, this refers to clean installs, so perhaps MS support personnel are referring to upgrading with Vista still in place.