Went to grab some example payments and I noticed a pattern
It seems that in any batch of payments, the first payment I send is free, and any subsequent payments charge the transaction fee.
I guess sending more than one transaction within a short time period requires the fee.
I normally send a few payments at once, as I'm paying out a bunch of members from our site
This is what sendmany is for. I highly recommend you use it: You can pay many people with a single transaction, and a single fee (if required).
What is sounds like is happening in your case is that the change from the first transaction is being respent right away, and respending right away is a DOS-attack-like behavior (e.g. an attacker would ping pong coin rapidly to generate traffic). Bitcoin should normally avoid doing this preferring to use older inputs, but if there aren't enough other inputs in the wallet to satisfy the payments without using the fresh change then it will use it.
If e.g. you have a single 50 BTC input in your wallet and you've been sending out 1 BTC payments you end up with transactions like 50->{1,49} ; 49->{1,48} ; etc. So if you simply do a send of 50 to yourself: {10a,10b,10c,10d} to break the input up, then the software should instead prefer to spend 10a->{1, 9}; 10b->{1, 9} rather than reusing the change right away and probably avoid the fees.
Either of these cases should be sufficient to avoid the fees in your case, and the sendmany puts less load on the blockchain as well.
