For those who don't know, SPF allows one to specify which IP addresses can send mail for a domain. Your VPS likely wouldn't match the range for whatever domain you're trying to send from.
Turns out I'm one of the lucky few (or silent majority) that had no problems whatsoever after getting my newly acquired ip off from a few lists. Google recieved my mail first try without even looking into spamlists.
...Maybe it helps that my domain is a relatively expensive one?
So currently it's not infeasible, just an uphill battle.
Another fun story, I once tried to contact a public authority and my mail was rejected. I then tried to contact the postmaster inbox, same thing. I had to use my gmail account and was initially met with a dismissive reply. Only after asking what the job of the postmaster incorporates if not helping users with delivery issues and whom else to contact I got helped reluctantly.