Yes, Core 0.11.2. I start it on and off when I need to do something with my wallet. Usually it catches up several days and then I do a transaction. This particular transaction was sent with 0.00013 BTC fee which seems reasonable?
It does in the abstract, but that is just abstract.
Currently, Bitcoin Core uses an algorithm to monitor the network and see how long transactions take to confirm and then uses that to determine what fee is needed to get a transaction to confirm quickly. If it doesn't have sufficient information since it had just been started, it could be miscalculating.
If you have the tx id, that might be helpful ;-)