Yep ... tried QTP open before browser and browser open before QTP ... no help. Yep ... have record and run settings set to act on any open browser - no help.
The ONLY way to get QTP to recognize web objects on the affected machines is to have QTP open the browser by using "Open the following address when a record or run session begins".
As I said, only some machines have this problem. I suspected browser settings of some sort but have not been able to determine any differences between machines that work as expected and those that don't.