You're right, this ISN'T normal. It sounds as if you know how to properly partition and install windows, so I have to ask... is it a legitimate copy of Windows?
If Medion (with whom I'm not familiar) give out "restore CDs", it's possible (but unlikely) that the hidden Windows partition has been messed with, making the CD copy back the spyware you'd just deleted. If the CD is copied, the problem could be right there. In any case, even if it's a legitimate full-install CD, I suggest getting hold of a CD from somebody else and installing from that (you don't have to activate, just see if it works).
You say you didn't install any third-party progs... does that include drivers? Do you mean you just installed XP, set up your internet, and started getting these popups? In that case I'd suggest having a look at the ISP's disc (if it's not a manual setup). If that seems harmless, reinstall XP and install a firewall BEFORE connecting your net cable. XP's Internet Connection Firewall should do the trick if you don't have another.
You also mention "the homepage that XP sets IE to". What page is this? I believe all version of Windows for several years have used msn.com as their default, is yours different?
If you can't solve the problem with any information given so far, please reply to this post with some information:
Internet Explorer's exact homepage
The precise version of Windows (start -> run -> "winver")
Every process listed in Task Manager
The details of your Internet connection (excluding username and password, naturally)
With luck, the problem will be glaringly obvious from those details.
goblinking