Since this error message is not generated by uddeIM the problem might be somewhere else.
Do you have lots (I mean really lots, say 1 mio.) of messages in your database? So Joomla's pagination may fail.
Another problem might be SEF or Caching. Some of these components store URLs and maybe there are too many "pages"?!?
uddeIM & uddePF Development
CB Language Workgroup
CB 3rd Party Developer