Stuart,
Again thank you for your help, I fixed it finally. Once again I tricked myself into thinking an issue is more complicated than it actually is, I forgot to change a setting in the PBX when I changed the voicemail DN with my service provider. Applications → Extensions → Extension # → Advanced → Mailbox, this needs to be “2223334444@SIP_Remote”
For future reference the PBX settings (for VoIP.ms in my case) are found here: MWI and VOIP Provider - #11 by jameelm
Man I feel so stupid right now.