Satoshi's Client has a set fee of 0.0005 BTC, although it enables you to "choose the fee". If you choose a lower one, youll get an error message once you actually try to send a tx. Sometimes you also have to pay more, like 5 times as much as the minimum fee (0.0005), dont know if that is somehow part of change?
As I understand, the Satoshi client selects a fee based on transaction data size, priority, and dust outputs. Only the data size fee is user-selectable; the client will enforce a minimum fee on low-priority transactions and transactions with dust outputs, but high-priority transactions with no dust outputs can be sent with no fee if the data size fee is set to zero (at least, I think that's how it works).