Obviously though the democratic vote of the miners is: Add a fee or GTFO.
Where did you get this assumption from?
Bitcoin has a free structure that seems to be working fine,
and most mining profits are from the coinbase reward, not the fees.
Just my uneducated thought process of logical thinking:
Bitcoin-Core normally deducts the needed fee from transactions bigger than 1 KB and from transactions that use just one input regardless of size, but it does not deduct a fee if you use more than one input but still land below 1 KB in size, as I found out by playing around with the "coin control" function after this "no fee deducted" thing happened to me.
Since Bitcoin-Core is the reference client that defines the standards my logical assumption is that those transactions are meant to be handled for free in the same way that transactions that need a fee are handled, which includes being confirmed at the same speed. Since this didn't happen and instead said transaction took 6 hours to confirm the logical explanation for me was that miners didn't follow the standard rules of the Bitcoin-Core client.
If it isn't the miners' fault, then fine by me I made a wrong assumption. Nevertheless a thing like that shouldn't happen as it is extremely inconvenient for the user. In my view a reference client shouldn't resort to just setting the standards in terms of pure technical functionality but also in usability.
As to Gavin's answer:
Thanks for that info, that is good to know. Also I already set the client to always pay a fee in the preferences right after this incident. My rationale though is that we shouldn't need to do this by hand. It should be default behavior if paying a fee is the only valid way to make 100% sure that transactions are handled in a timely manor.