I manage and develop a lot of InfoPath forms and my users get this error All.The.Time! And I'm still insisting on them opening the majority of our forms via a link, so I do have a fix that works every time. It's bizarre, but it works.
Go to "security and trust" in the form options. You want "domain" of course. You'll find that either the "automatically determine..." checkbox will be selected or the "domain" option button will be selected (without "automatically" checkbox selected) Whatever is set, do the opposite (even though, in theory, they both do the same thing).
For example, if the "automatically determine..." checkbox is set to true, then UNselect that and just make sure the "domain" option button is selected. Re-publish the form. If the "automatically determine" checkbox is not selected, then select it and re-publish the form.
I realize this makes no sense since both of those options do the same thing. But this fixes the problem for me every time.
I am in the habit now of testing a form when I publish it to make sure it opens properly.