All right, it finally works
I looked into my backup HDD images and found a Steam installation dated 19 August 2015, from a Pentium 3 build. I just copied it to my P3 laptop and made a steam.cfg file, containing: BootStrapperInhibitAll=Enable (so it will block any potential updates) and it is working and logging into network without any problems
I will look for other Steam backups, maybe I will find something newer, that still works.
I wonder how long the protocols of new and old version will be compatible so connecting will be still possible.
I can finally play HL1 deathmatch using Steam on P3 laptop with ATI Rage 128 Pro (well, actually the performance of retail Half-Life was stable 30+ FPS (Win98), and Steam version is like 3 FPS... probably not enough RAM and constant HDD swapping; I guess a Dell Inspiron 8100 with P3-M 1.2GHz and Radeon 9000 will be much better)
For really old PCs there is alternative to Steam, which works with retail copies of Half Life/Goldsrc games - https://won2.net/
// Little update:
I looked for more backups of my HDD, laptop, virutal machines and found more copies of Steam installation. Even 2016 versions still work (still you have to make that steam.cfg file).
Installation dated 02 August 2016
(18.104.22.168) works fine on Pentium 3. But you can't enter Store tab, you get message "The Steam Browser is disabled. See this Support Article for more Information
(that's not a big problem, anyway... you can still access the library and you can use "Small Mode").
Installation dated 31 March 2016
(22.214.171.124), a bit older, works the same way, without steam Browser.
Installation dated 19 August 2015
(126.96.36.199), the oldest I have, also works fine, it even has working Store tab (apparently it uses od Chromium version without SSE2 requirement).
So, as you can see, Steam has been working out of the box without SSE2 half a year ago, so the incompabilities have been created recently. I checked today's update and it doesn't work. I don't know if they will bring back SSE1 support (there were some moments in 2014 when SSE2 was required, but they later removed that requirement)
// Another update:
After installing proper ATI Rage Mobility drivers on my P3 800 Presario laptop, the gameplay is smooth, just like in the retail version