There is very little troubleshooting. It either works, or it doesn't.
Don't believe a word the ISP says - ISP technical support routinely lie about most things. All they want to do is get rid of you so their call stats look good.
When the messages are stuck in the queues, what does the additional queue information box say?
Simon.