One thing it may be worth triple-checking is that the copies of OmniFocus on your various devices are all up to date. (Maybe there's more than one copy of OmniFocus on one of your Macs and an old one gets launched occasionally?)
I don't have any hard evidence to go on, but the symptoms you're describing are roughly similar to some problems that existed in earlier versions of OmniFocus. It's been several months since we got support mail about any of them in any significant quantity, though. Most of our customers aren't seeing this happen any more.
Current release of OmniFocus (at the time of this writing; forum posts have a long lifespan) is 1.7.5, which you can grab on
this page.
Current release of the iPhone app (check the bottom of the Settings screen) is 1.6.1.