Hi Gareth,
Ensuring you have SPF setup exactly as they wish, that the validity of the messages and content are good will get you a better reputation.
If you've been sending a lot of questionable messages, your IP reputation will be lower preferenced during peak times in comparison to others.
You may have to jump through hoops - but it really is the only way (believe me, coming from the back of re-addressing all of Websense's hosted infrastructure, where they didn't copy over the rep and within 10 seconds of the IP change we were being temp failed

)