Have you seen this thread?
No, I haven't (I actually found it quite pointless to google using keywords like "explorer" and "desktop", so I never looked too hard).
And ... tada! ... it's exactly the explanation I was looking for!
It's caused by the desktop toolbar in the task bar.
I had even forgotten I had that toolbar active.
Thanks a lot!
1) I forgot to mention above that this is XP SP3 with the classic shell. Just for the sake of completeness.
2) Yes, my desktop is a mess. All those folder icons really are folders sittiing on my desktop.