Mails not leaving mail queue

We have some problems with mails getting stuck in mail queue. I have read other issues related to this problem, but none of them seems to match our problem.

It seems that some email are sent, but a great amont of mails are not sent(ex creating issues, commenting issues etc). We can send test emails from admin pages and flushing the queues works well. I see from the log file that the following error is printed several times and might have something to do with it:

2006-05-07 14:03:50,545 INFO [com.atlassian.jira.mail.MailThreadManagerImpl] Couldn't find Notification Instance record for issue 11050, so can't thread related email