I usually set the fee at 0.03 mBTC and ~80% of the time it goes through. When I am asked to set a higher fee, it won't go through below 0.1 mBTC. This happens even with transactions below 1 kB.
I wonder if the minimum fee depends on which node I'm connected to?
Yes and no. The fee is in effect an incetivisation for miners to include transactions in the blocks they find. However, the fee is dictated by the adoption of the reference implementation of the Bitcoin protocal (ie nodes and miners). A single node will not be about to change the minimum fee - it is a consensus from miners and nodes that agree to have a different fee structure that will lead to different fees.
At the moment, the current minimum default fee that is accepted is 0.00001 per kB. Anything lower doesn't really make a difference, usually the transaction will either be considered non-standard and take a while to confirm or depending on the parameters it will be taken as a no fee tx and still be confirmed (depends on your inputs/outputs and size).
