This can certainly happen, but it can be normal or caused by an error. Thus, you need some further investigation. If you see anything odd in the server logs (not sure that you will, but if you do), you need to open a PMR for those to be analyzed.
The Apple syncs mail in two phases. Phase one gets a 512K plain text version of the mail. Phase two asks the server for the whole, right text version of the mail. If phase two fails (error or timeout), then you will see the not downloaded message (sometimes, even if phase one worked completely). This could be a connectivity problem or there could be some errors on the server.
iPad Message has not been downloade... (Alfa Tecnologia... 30.Sep.11)
Feedback response number RSSN8M8HGL created by Robert S Sielken on 10/01/2011
. . RE: iPad Message has not been downl... (Robert S Sielke... 1.Oct.11)
. . . . External Server URL (Alfa Tecnologia... 6.Oct.11)