Sad to hear that - though I left hellstra years ago.
I never rely on any ISP to store my email because sooner or later you will want to switch which means cancelling a contract - I've switched 4 times in 5 years. For this reason I signed up long ago to Apple's .Mac (now MobileMe - I also carry an iPhone) on the basis that Apple is likely to be around longer than most of the telcos here. You could say much the same for MSN or GMail.
Take a gander at
http://bc.whirlpool.net.au/ before you sign up with any ISP.
I've been on Internode for 2.5 years and they have been perfect.