Longer answer (disclaimer: I'm a former PCI QSA). You can, of course, do whatever you want to with the credit card data at the risk of not being PCI compliant. Small startups are rarely at risk for a breach, but I'd personally prefer not to be in a position to deal with that liability. As it relates specifically to those companies, they need to apply to be on that list. I know that Recurly is currently working on it and Chargify is still in private beta, so I'm assuming it's something they're working on. That said, I have confidence that some of these companies will "do it right" and obtain PCI compliance/validated service provider status by the time it becomes a legitimate concern.
I've talked to both Recurly and Chargify directly. Recurly is apparently PCI Level 2 compliant and working on the external audit to reach level 1. Chargify is outsourcing storage ( http://chargify.com/blog/adding-payment-gateways-while-maint... ) which addresses a lot of concerns, but I'm not sure if they've gone through the necessary compliance process otherwise. As for CheddarGettar, the only mention of PCI compliance I can find on their site is this - http://support.cheddargetter.com/discussions/questions/39-pc... - which doesn't really indicate an understanding of what is actually required to be compliant. I can't comment on Spreedly as I didn't look at their solution, but I do know one of the devs previously worked at a large PCI shop.
So a service provider like these guys can technically be PCI compliant, but not be on the service provider list if they haven't applied to be. If you use them, though, they best be on the list by the time you reach the point that the PCI assessor (they don't like to be called auditors. ;)) is knocking on your door. This isn't likely to be for a while for most startups, though.
In some of the early data I've seen in a survey I'm doing (shameless plug: http://www.untitledstartup.com/2010/02/payment-security-surv... ), most companies are implementing their own system directly to paypal or similar, but have not actually gone through the process necessary to become PCI Level 4 certified. Most feel that the benefit of keeping the payment flow on their site is more important than the relatively small risk of being compromised. Can't say I agree, but I'm more paranoid than most.
Also, why reinvent the wheel? PayPal and Google Checkout are major vendors with PCI certifications who handle the entire transaction process. Why not use them to handle all the risk? You get a transaction id and collect your money through them. Never touching the sensitive financial information.
I am interested in doing some re-occuring billing stuff my self so do post back with your experiences with which ever provider you go with. Best of luck :)
We ultimately chose to go with recurly, but are going to look at chargify again once they stabilize a little bit. Recurly is not on the list, but in the process of doing so (I just emailed them ~10 minutes ago specifically about being a validated service provider).