Just checked some old NT 4.0 CDs lying around. No luck with that.
Nor was it in service packs 3, 5, and 6.

I found a reference for "IE 4.0, 4.01, or 5 on Win95B". So Win 95B may be the right time frame to look for.
The Win95 CDs I have lying around all have a 4.70.0.1155 IE, but no browseui.dll. I'd think that 4.70 is later than 4.01, so I'm a bit sceptical that browseui.dll existed for 4.01 at all.
Win98 is too late, it's got a browseui.dll with a version of 5.0.2614.3500 (which happens to be the same version as that of iexplore.exe).