I have come across this a couple of times recently. Paradise email user having problems sending mail - gets something like a 552 error from smtp.paradise.net.nz http://paradise.net.nz/. Username and password OK for receiving email and works on web mail.
The solution I have found in both cases so far is to replace smtp.paradise.net.nz http://smtp.paradise.net.nz/ with smtp.clear.net.nz http://smtp.clear.net.nz/ and emails then send OK. vodafone would probably work too. I think this is just more evidence that Vodafone is trying to kill off the paradise domain….