I found a good, cheap alternative to OmniFocus in ToodleDo. It is browser-based (it doesn't get much more "cloud" than that), but they also have an iOS app for offline use. I've been using it for a few years now and have had little complaints even at their prices (free to a fraction of OmniFocus).
As a sidenote, OmniFocus does support cloud-based syncing. From the product page:
You can’t accomplish your goals if you
don’t have them with you. OmniFocus
synchronizes your task database with a
server or disk, so that all of your
Macs, your iPhone, and your iPod Touch
are up-to-date. Sync over your local
network using Bonjour, through the
cloud using MobileMe or any standard
WebDAV server, or even with something
as simple as a USB drive.
I believe this is a recent development since their iOS apps. OmniGroup products are not cheap, but they are definitely worth the expense.