Is there some threshold number of confirmations or amount where there isn't a compulsory transaction fee? My earliest incoming was about 1.1 BTC with a few hundred confirmations from 10 days, yet when I sent a 0.02 BTC transaction, it still demanded the transaction fee.
Or does the sit still means that my wallet/address must not have any transaction for at least X hours before sending?
It means the specific coins you use must have been in your wallet (have not moved) for a few hours. The client's logic in selecting which coins to use is a bit mysterious, and it won't always find the best combination of coins to use. It is not so much the client's fault -- it's also an issue that which coins are best depends upon what you plan to do in the future, which of course the client cannot know.
If you have a lot of small incoming transactions, you may need to do one "clean up" transaction. You can manually connect to a bitcoin client known to accept transactions with no fee, do a single "clean up" transaction, sending all your bitcoins to one address with a small fee, and then be very patient and hope the transaction gets to the client and then a miner picks up that transaction. It can take a day or so, but you should only need to do it once. Then just stop doing whatever created the mess in the first place.
Try this:
1) Create a new bitcoin address.
2) Backup your wallet.
3) Set your transaction fee very, very low (say, .005).
4) Start your bitcoin client with this on the command line:
-addnode=173.242.112.53
This connects a no-fee client run by Luke Dash Jr.
5) Create a transaction to transfer all your bitcoins to the new address you created in step 1. You may need to subtract .005 or so for the fee.
6) Go away for a few hours. If you're lucky, the transaction got into a block and all your bitcoins are now in one place. Let them sit there a few more hours and your problems should be solved.
If the transaction doesn't go through, you can revert to the saved wallet.dat file to undo the transaction.