Most solo miners and mining pools currently treat any transaction that has a fee that is less than 0.0001 BTC (0.1 mBTC) exactly the same way as they treat any transaction that has no fee at all. A fee of exactly 0.0001 BTC can take some time as well...
I usually go with a 0.00015 or 0.0002 BTC (0.2 mBTC) fee just for good measure
Oh, didnt know that. I usually send with the .0001 and never had any problems.