Hi Peter,
I'm replying to you because Bob, whose been replying to you won't be back until next week.
Unfortunately, I'm just as baffled as what's happening in you case, but I'll try to offer some addition possibilies.
First, when normally starting TelnetPro.exe, there is no attempt to do any connnection, so there should not be any issues about connections or firewalls before the TelnetPro window pops up. The exception is if you have the autoconnect set for one of your hosts. If this is the case, make sure this is turned off for all the hosts, on one of those occasions when you get the program started, of course. This will let you eliminate connection issues as the source of the problem (or confirm it).
The behavior you describe sounds like Windows is waiting for something over the network, like a resource, permission, etc, that it needs to load the program. This would explain the variable time the program takes to load; it's waiting, and timing out, perhaps multiple times, to get a resourse that is not reliably available over the network. Normally, all the components of Pro should be installed on the local (C:) drive. Could any of the components be installed in a directory of drive that's shared across a network? Perhaps Windows needs to check permissions to access a directory from a remote Domain Server.