This seems to be inconsistent behavior though. I've paid a 0.0001BTC fee (roughly 6 cents) and had transactions go through in less than 10 minutes.