OK, after a bit of research we've decided on RealWebHost
as our new hosting company.
Our present hosting company has finally given us access to our existing site so we can backup our data. Gee, isn't that generous of them? After all, it's only been 3 days since the problems started. Now that's quality service.
I expect we'll have more to say about our experiences (and those of Whaleoil.co.nz) once we've moved our site to RealWebHost.