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.