Your post prompted me to take a look at my Tiscali e-mail storage.
I've also been with them since the screaming.net days.
I do not pay any extra fees but I notice that my mail storage capacity is 25Mb.
I also wonder why you need to keep your mail on their servers??