I do not have a (working) N9 to test so this may be a BS but the first thing I would try if I had that problem would be moving old emails to a dedicated folder. I assume you have tried that already though as that seems such an obvious thing.
Just an opinion: Delete everything, then create account again In Accounts >> mail >> At downloads select>>> headers only log in, sync, then change back from <<<headers only>> to <<full messages.>>