To my sheer and utter surprise, my problem is solved. I've given Otto42 my details for FTP and WordPress admin, he looked inside, noticed that my /upload/-folder was chmod 755 (and not 777), changed it to 777, and now the upload works.
It's a miracle, since I've done that myself multiple times in the past too, but always placed it back to 755 if it didn't work, since (to the best of my knowledge) 777 would allow some vulnerabilities (please let me know if such is not the case).
Maybe the chmod 777 trick works only in combination with worpdress 2.5.1; it might be the case that I've only tried 777 with WordPress 2.5.0.
Anyway, my route to success seems to be:
* do a clean install of WordPress 2.5.1 (keep the database, remove the files on your server)
* chmod the folder /httpdocs/wp-content/uploads/ (and its subfolders and files) to 777
One thing: I've mass-chmodded the folder uploads with filezilla, using the option 'file properties' -> '777' and the options 'apply to all sub folders' and 'apply to folders and files' ticked. Maybe this doesn't work properly, keeping certain folders or files in their old chmod state? It's worth to investigate on this if the problem persists in your case.
* upgrade to 2.5.1