The code for the Bitcoin-Qt wallet (and some other wallet systems) require a fee if the bitcoin input being used in the transaction is too small and new. This is done to prevent someone "spamming" the network by sending a large volume of very amounts of bitcoin back and forth among a number of addresses they own. The protocol itself doesn't require this fee, and some people (such as Satoshi Dice) create their own programs for pushing transactions to the network so they can avoid this fee. Many of the peers that you connect to may not forward your transaction to the rest of the network and some miners may refuse to include the transaction in any blocks they add to the blockchain without the fee. This can result in a very long wait for the transaction to finally receive a confirmation.
I've had otherwise high priority transactions with aged coins and sufficiently large outputs take several hours and many blocks to get their first confirmation. If the reason you are sending coins is at all time sensitive, you want to make sure you include an appropriately sized fee. The Qt-client uses a formula to try to ensure the fee paid is appropriate to the size of the transaction, but sometimes the big mining pools and the Qt-client disagree on what an appropriate transaction fee is. They especially tend to disagree when the fee is zero.
Satoshi Dice includes fees on all of their transactions (even when they just send a single satoshi to let you know you lost). I don't know that it could work anywhere near as well if it did not include fees in outbound transactions.
