Specific feedback on GoDaddy / Rackspace
pedalpete: I've had Godaddy, Server Beach and The Planet. I wasn't that happy with the Godaddy because I found the management interface a real pain to figure out. Same with the reporting tools.I just bought an SSL cert yesterday from GoDaddy to use on my Server Beach server, and that brought back the memories of how difficult it is to get around inside godaddy's products.I really like the reporting features from The Planet, and the pricing was good. I just figured I'd try something else, and I've been pretty happy with Server Beach, but find I just run mpstat/ps to get server stats, rather than looking through a management console.As far as php mail(), my understanding is that it isn't the server that is necessarily the issue, but rather domain, and spam filtering. 
I'm using http://swiftmailer.org for mail from php, and I've been quite happy with it (although I haven't actually launched the service yet, so I'll have to see how it goes).I can't comment on Rackspace because I haven't tried it yet, though I'm thinking of going Cloud if the project I'm currently working on gets traction.