[Brian]

Gabriel, how many Macs are you syncing OmniFocus between? If it's more than one, I suspect I know what's going on.

The message links that Mail creates and sends along to OmniFocus work on the Mac that creates them, but they only actually work on that Mac. (It would be awesome if Mail made sure the IDs assigned to each message was the same on all your devices, but that isn't currently the case.)