You've tried most of this already but have you tried this process?
*Call O2 voicemail setup on 1750 and wait till you're told your O2 messaging service has been switched on (this step may not be essential)
*Then phone O2 voicemail itself on 901 and press "*", then "4" for manage your mailbox settings, "4" again for change your security settings, set a new pin (even if it's the same one you had before), confirm the pin, then in the same menu press "2" to enable the pin (meaning you'll now need to enter it in future to access 901)
*Now on your iphone4 go into "Settings", then "General", then "Reset", choose "Reset all settings" (this will lose your pin, passwords, wifi, background...) but it will retain all apps in order, photos, text messages etc. NOTE: Tried just "Reset Network Settings" first, but this didn't help.
*Once the phone restarts after the reset, setup any necessary pins or passwords again and check your voicemail tab in the phone app (for me it went straight in, no more annoying setup screen!)
*Now just tidy up your phone settings to how you like them and redo wifi passwords etc..... You can also go back into 901 and change the pin and turn pin access for 901 off again if you like. NOTE: May take a while for it to detect any voicemails you leave yourself to test it."
