Use
http://cointape.com/ for finding out the best fee for every KB according to the current number of uncomfirmed transaction.
It might be because of the ongoing blockchain attack
Yes, I think that backs up my calculations - but like I say I am really tired and would appreciate someone who is less so to either back my numbers up or show me where I am going wrong.

most companies probably just have a fixed fee and their customer support isnt usually doing more than repeating standard answers
in recent days (hours), the number of unconfirmed tx spiked, this allows the miners to cherry pick the highest paying tx and still fill a block, so they do.