As far as I can tell, transactions are not prioritized according to fee size. Paytxfee just ensures that you will meet the fee requirements (and it isn’t guaranteed to do that). This does seem to be contrary to what Satoshi and sirius-m have implied, but I can’t find any prioritization in the code.
Re: Prioritized transactions, and tx fees
Participants: theymos