I am not 100% certain but looking over my tx history I have never seen a fee.   Still if I am wrong I will happily update the list.

My theory is that exchanges tend to have lots of old coins.  They can use old coins in outgoing tx (high priority) and overtime the new coins become old.  It worked fine until recently.  They got high priority without ever paying a cent (except maybe the occasional "spam" tx).  Now a tx w/ old coins and no fee may get bypassed for 2 to 20 blocks due to the number of unconfirmed tx with a fee.  


Yhe point of the thread was to create a discussion and hopefully encourage providers to give the users THE OPTION.  Sometimes I may want to pay nothing and be comfortable knowing it gets into the block eventually.   Sometimes like when paying a sale I want it in the next block.  Period.  If that takes 0.0001 or even 0.01 BT I would rather pay it then wait an unknown number of blocks.  Even if the default is no fee, users should always have the option of paying a fee (or an increased fee) otherwise they have no control over their transactions.