A Visio file hosted on SharePoint and being exposed through a Visio Web Access web part intermittently displays the following error message when you try to open the document from the browser (in both Read-Only and Edit mode):
To open this diagram, your computer must have a version of Microsoft Visio 2010 installed and your Web browser must support opening files directly from Visio in the browser.

The strange thing is that this typically works, however intermittently the Visio will not load in the web part until you close the browser / restart, and / or clear the browser cache, and then this behavior tends to follow (I can't prove causality).
I've found suggestions regarding 32 bit vs. 64 bit versions of Visio being installed on the machine as well as this error appearing when 64 bit Internet Explorer is used, however neither of those are possible issues here (32 bit Office Professional Plus 2010, 32 bit IE, Windows 7).
When this error has appeared in the past it "randomly" resolves itself, but that isn't a real fix.
Does anyone have any insight into how to resolve this?