Here's a really simplisitc test we've done in the past. Have the Cisco user call a Mitel phone direct, no auto-attendant. With the Mitel user listening, have the Cisco user press 1-9 on their phone. If the Mitel user hears the tones, then it should be working correctly.
It sounds like the SIP trunk provider is having an issue with your local PSTN provider. Since all your calls come in PSTN, they should all be treated the same. I would have the Cisco user have their SIP provider do an active trace, and look at the SIP messages that should contain the DTMF, as their transmitted to the PSTN.