Code:
iptables -t nat -A POSTROUTING -m statistic --mode random --probability 0.5 -m state --state NEW -j SNAT --to-source X.X.X.X
iptables -t nat -A POSTROUTING -m state --state NEW -j SNAT --to-source Y.Y.Y.Y
Each new outgoing connection will "randomly" be Source NAT'ed to either X.X.X.X or Y.Y.Y.Y
This is assuming you have 2 IP addresses. If you have 3, you'll need to:
1) duplicate the 1st rule
2) adjust the source IP in the new rule
3) adjust all instances of 0.5 to be 0.333333333333 etc
You may wish to include a -d argument in there too so only outgoing connections to the host that's causing you problems is randomized
