It's possible that other nodes on the network were broadcasting a high number of pending transactions to you, which would temporarily increase your local relay fee and result in this error. I haven't looked too deeply yet but that is the only other obvious possibility I can see. Has this problem re-appeared at all since the first times?