I've been experiencing the very same thing - 5 or more spam messages per day - ever since migrating from dot Mac to iCloud. And like the original poster I've had my account since the iTools days.
The Mail app on Lion flags the messages as junk, as does the iCloud web interface, but my iPad and iPhone receive the messages without hesitation, no matter how many times I've flagged those senders as junk. I have to remember to turn push notifications off when I go to bed, or else I'll be awaken by 5 or more spam messages arriving throughout the night. And again, this did not start until I migrated to iCloud last Fall.
I wonder if this isn't an issue only affecting those of us whose accounts remain @mac.com instead of @me.com. I've tried setting my account up as the latter on my iPad, but once added it changes it back to @mac.com - sabotaging my experiment.
Per
Apple's instructions, I have forwarded the messages to
spam@me.com, although I'm not sure what good that will do as they claim marking the message as junk in Mail and the web interface essentially does the same thing.