Just an updated. Called support and this was pointed out to me. If Exchange 2010 has been installed, which in my case it had been, the following happens.
If you look at the Notice message that's being sent from Exchange to the 3300, it has both the to and from message addresses as being from the corresponding extension number. This is what has changed in SP1, previously it would say the message was from the Exchange server itself.
Mitel basically told me that it was something Microsoft would have to permanently fix, but they gave me a work-around.
By adding the extension numbers to the "SIP Peer Profile Assignment by Incoming DID" form, the system will accept these notify messages. The only down side to this is that the message key will not work, i.e. the envelope key. Because the message says that the extension turned its own light on, the message key will just loop you.
This did work for us, and we stopped getting the 404 error messages and MWI's turned on. I have no idea if MS will actually fix this or if they intended it to be that way for some reason. (MS support forums put the blame on Mitel, so who knows really.)
