I simply set my max zimbraPrefMailItemsPerPage with zmprov to 600 and my pain went away. It was on 5.0.8 so i am not sure if you can do this with 4 also.
Please be aware that this is sort of a hack. I have no idea if it harms your installation or WebUI in any way. ( Or in other words: "Dont do this at home kiddies!"

)