Before you suggest I check out this topic: http://www.magentocommerce.com/boards/viewthread/246247/
I am running Magento 18.104.22.168 and this has the mentioned fix.
The problem seems to be more to do with whatever Magento does to generate this message. It is not that it keeps showing the same message, it’s that the message keeps being re-entered in to the database (specifically anytime I flush Magento’s cache), but I do not know what process is causing this or how to stop it.
Any help would be greatly appreciated.