Lotus Notes Error – “Specified Network name no longer available”

I work for a bank who is using Lotus Notes email and during the transition from Windows XP to Windows 7 the Lotus Notes client was upgraded from Client 8.0.2 to 8.5.3.

Given that these were the only two things that changed, our clients now randomly encounter the following error when running the Lotus Notes client:

Specified network name no longer available.

The error is extremely intermittent as to the affected user, however, the problem seems to consistently happen shortly after a user logs on to a workstation and launches the Lotus Notes client.

There is nothing written to the Windows or notes logs. The desktop is being redirected to a server as are the home drives and the Notes data directory. This has never, ever been an issue prior to the upgrading to Windows 7 and upgrading the client.

One thing that we notice (since the profiles and home directories are redirected) is that if we unplug a network cable with Lotus Notes running, the redirected desktop disappears (as expected) but Lotus Notes client does not give the "Specified network name no longer available" if we try to access a database in the disconnected state. It waits and keeps trying to communicate with the server. So we cannot duplicate the error forcefully, and it seems that a specific action is causing the error.

Has anyone seen this before, and if so how did you fix it? Domino articles seem to indicate a latency issue, but we have pretty much cancelled that probability out.