I have more than 6000 emails in my Gmail IMAP and Modest (the default email application in 4.2008.23-14 and later) doesn't have any problems with it.
Do you have "Download headers only" activated?

You can start an X Terminal window and enter
export "CAMEL_DEBUG"="all"
to enable the debug mode of the mail library, and after that
/usr/bin/maemo-summoner /usr/bin/modest.launch showui > log 2>&1
to start the email application. Then try to connect to the mailserver. A logfile named "log" will be created, maybe it contains some errors (maybe not).