ServerBeach will allow you to set the TTL to 5 minutes (or less) if you ask!
But, before you make that leap I suggest you think seriously about it. If you are going to leap to RackSpace then okay, but I don't think that is what you have in mind.
ServerBeach has one of the best networks available, it is a RackSpace network rebadged. Jumping to some cheapy host with an unreliable network will most probably cause you more trouble than you could ever imagine.
My advice, you are already in the right environment, work with the people you know and get them to give you what you need!
ServerBeach don't do DNS hosting, unless you're hosting it on your own server, which is generally a very bad idea. I found a dns host that does allow low TTL's. It's [dyndns.org...] I emailed support and they sent me this:
"The advanced interface of our Custom DNS service allows you to set any TTL you wish. You can set a TTL of 60 seconds, or one week, if you want, it's entirely up to you."
Their pricing is around 25 bucks a year. So looks like I'm set.
Mark.