The actual size of the database is not an issue, and never really has been.
I think the issue is the number of rows in the database... having more rows slows things down because this version of MyBB queries the PM table every single time you load a page.
Having the messages stored outside the DB wouldn't work because there would be no efficient way to query them.
MyBB 1.2 caches your PM statistics, so I'll consider increasing the limit after I upgrade.
/ 
