Loading of cached messages loses order (was Message Store cache pagination display is broken)

Once the cache is full no new messages are displayed, what should happen is that new messages are inserted in the front & the oldest ones popped off.