You say, "'Starting Windows' appears, then, absolutely nothing". Do you mean the screen just goes blank? If so, I've had this problem before, and after waiting for around 15 minutes it eventually proceeded with the install.
Also, have you tried doing a PXE install of Windows (installation over the network)?
Install Linux Ubuntuu on a brand new CD
Boot from the CD into X-Windows
You should be able format the HDD from there (I would also repartition it just in case).
Then reboot and boot from the Windows CD and try it again.
**edit oh wow just noticed this was my 250th post I will finally discover the mysteries of the members marketplace!!!**