Apple mail just plain sucks. It was horrible as mac.com. Emails would sporadically disappear into the void from all synced devices and the server, as if they never existed. During that period the promise was me.com would fix it. Unfortunately the problems persisted on me.com. I'm sad to hear that iCloud has the same problem. Perhaps Apple has bitten off more than they can chew.
I don't think bitten off more than they could chew, just maybe more than they prepared for. The whole web-sync aspect of Apple's products has always been buggy... they just never seem to throw the adequate resources at it to fix it. I was hoping it would be different with iCloud, since their entire customer base is now starting to depend on it with their most critical data. I'm not sure they get it yet.
They are essentially treating this aspect of their products more like a nifty add-on than mission-critical. One gets the impression that it exists primarily to sync up music, movies, and TV shows, and that the calendars, contacts, mail, etc. are kind of ignored. I sure hope I'm wrong, but that seems to be what I'm seeing so far.
Luckily (knock on wood), I haven't noticed any data loss yet. But, I only have an iPad and one Mac in my little syncing eco-system. People I know with more complex setups (multiple macs or iOS devices) are telling me they notice contacts or events disappearing from iCloud or not syncing properly, etc. So far, the only problem I've had is a number of times, having to kind of give a 'push' to the system to get my bookmarks to sync (basically, go to the other device and add something to get synced up with the first device).
Come on Apple, please don't let us down on this one! Hire a few more good sync folks and get on it. Too many issues in this area actually could ruin the whole reputation of the Apple eco-system. Your market is more than selling phones and movies/music, especially given these are 'smart' phones. Get a bit more serious about your entire eco-system again!***
*** For example, Apple ditched the server line and nerfed their server OS, apparently to focus on consumer products more, or because they didn't think sales numbers for those products were good enough. They seem to be nerfing some of their pro-product lines (software and hardware). IMO, this is not very smart, as the whole eco-system is more complex than the sales numbers in the spreadsheet might tell.