For what it's worth, you don't have to generate transactions with fees. However, transactions without fees might not be processed by the miners until they reach a certain age. The priority of a transaction is based on its inputs' age, values, and the overall transaction size as sum(age*value)/size, at least in the default client. Once that reaches a certain threshold of block age from the inputs, it will be allowed by the default mining code to be processed as a free transaction, as long as there aren't many higher priority transactions ahead of it.