My mom and I are experiencing the same problem also, with different iCloud accounts that were migrated from MobileMe. I have tried nearly everything suggested in this thread short of creating new iCloud accounts.
I suspect the problem is not so much in the iPhone as it is on some, but not all, servers in the iCloud server farm.
I believe that iCloud email push works by performing a long-pull PING from the Apple mail server, which is a special type of PING that takes about 10 minutes to reply if there's NO mail. If mail arrives during this ~10 minute window, then the Apple mail server your iDevice is tied to for the session (i.e., some server in the iCloud farm) should send an instant PING reply to all your iDevices with an outstanding long-pull PING in the queue. This reply tells the iDevice(s) they have a mail ("the push").
Basically, your iDevice is PINGing Apple's servers continuously, 24/7. Either the specific server cluster your iDevice is tied to forgets to reply, or the iDevice itself stops continuing to PING; it's probably one or the other. Some of the iCloud mail servers may not be handling the long-pull PING consistently, and that may be way the iDevices intermittently stop getting "pushed" emails until Mail is restarted or the iDevice gets rebooted.
MobileMe push email worked flawlessly for years until I migrated to iCloud. Within days of migrating to iCloud, the push featire began working intermittently on my iDevices (usually stopping at night until Mail was relaunched in the morning). The problem is NOT iOS 5.0, it's something tied to: the iCloud migration; iCloud account itself; and/or iCloud server farm and/or the specific cluster of servers within that farm that my account might be tied to (hence, why some people who re-create their iCloud accounts claim this fixes Push notifications). And I believe that 'something' in the iCloud farm is a failure of the long-pull PING on SOME iCloud servers, but not all of them. That is why some but not all MobileMe-to-iCloud migrators have this push problem, probably because some but not all servers in the farm have an inconsistent configuration issue. It may be that MobileMe accounts, when migrated to iCloud, are permanently assigned to a range of servers in the iCloud farm. Hence, it's luck of the draw whether your migrated MobileMe account is going to have intermittent push failures.
Hopefully someone from Apple reads this message and thinks about whether this is a possible root cause, unless the root cause is already known to be something else! And I hope it gets fixed soon. Turning off push is an unfortunate solution to a great feature that worked perfectly for years under MobileMe!