Thanks for the suggestion, it does seem to fix the problem, providing I leave it on 2G only. If I switch back to 3G, the problem re-occurs, albeit seems to take a bit longer to happen. 2G is fine for calls and SMS, but if I want to use high speed data, this is a bit of a pain. Also Telstra has broader coverage on 3G rather than 2G.
I also noticed that once it has "gone deaf" to the network, the "Search networks" never finds any mobile networks either. Also, I cannot change the "Use only 2G networks" setting any more.
My Defy+ model number is MB526.