Fixed the problem
I have had the same issue described here.
The problem stems from the fact that the 'Mail' app stores messages on the internal memory only - does not allow one to move it to SD storage card. My office email quickly fills up the small memory.
I download a fee mail app called 'K9' - this one can be installed on the SD card and stores message there as well. K9 is decent mail client.
I now only use the 'Mail' app to sync my contacts and calendar (with my office exchange server).
This solved the problem for me and a friend who was having the same issues.