iPhone and iPad not downloading all iCloud emails
I somehow managed to work around this. First, I copied all my mail in my iCloud inbox to a folder. Then I copied all mail older than 1 year back to the inbox and let both my iPad and iPhone sync. After this was done, I copied all remaining mail back to the inbox and let my devices sync again.

Now all email is synchronized on both devices. Don't ask me how or why though.. :)