We have had Nokia Lumia 625 phones at work for about 9 months and all but one would not send or receive MMS. I contacted our corporate account manager at Telecom twice but he was not very keen to help fix this problem until we suggested that as they were not providing the contracted service it would cost them replacement phones if the problem wasn't fixed quickly. We also know of another company that we work with on occasion that had the same problem (totaling about 100 phones) and on suggesting that to our account manager they became very helpful.

Unfortunately they couldn't fix the problem but while on hold again I started fiddling. I decided to setup a completely new access point using the info from the phone that did work and blow me down it worked. I have now done the same to 5 phones and all have been able to receive and send MMS since.

Here is a detailed steps of what I did. I have a feeling the settings on the Telecom NZ account are the same, it seems that creating the new account is fixing the problem but checking that the settings in the old one are correct is not fixing it.

Go to Settings, Access Point, Add or + depending on your phones update status
Give it a name - I used "Telecom WAP"
In the "Internet APN" section
       - set the Access Point Name to "wap.telecom.co.nz"
       - that is all that you need to do in this section
In the "MMS APN" section
      -Set the MMS access point name to "wap.telecom.co.nz"
      -Set the proxy address to "210.55.11.73"
      - Set the Proxy port to "8080"
      -Set the MMSC address to "http://lsmmsc.xtra.co.nz" (the l is a lower case L)
Click the tick to save
Click on the newly created account to make it active
Give it a try.

I haven't deleted the old Telecom NZ one.