What to do about Steam window/taskbar icon not showing up after a reboot?

I would start off disabling all other applications from auto-starting and doing a "clean boot" and only having Steam be the ONLY application configured to auto start. Your comments only state that you've disabled Steam from auto starting.

If a clean boot with only steam running as autostart does not cause the issue then something else that is running at the same is. The fact that it has "followed" you across different machines and OSes lead me to believe that it is something else that you are installing/running also at startup.

https://support.microsoft.com/en-sg/help/929135/how-to-perform-a-clean-boot-in-windows.

Sign in to the computer as an administrator. If you don't have an administrator account, you can create one. Create a local user or administrator account in Windows 10. In the search box on the taskbar, type msconfig and select System Configuration from the results. Search result - System Configuration

Important If the computer is connected to a network, network policy settings might prevent you from following these steps. Only use the System Configuration utility to change the advanced boot options on the computer with guidance from a Microsoft support engineer. Using the System Configuration utility might make the computer unusable.

On the Services tab of System Configuration, select Hide all Microsoft services, and then select Disable all. System Configuration - Services tab - Hide all Microsoft services check box checked - Disable all

On the Startup tab of System Configuration, select Open Task Manager. System Configuration - Startup tab - Open Task Manager button Under Startup in Task Manager, for each startup item, select the item and then select Disable.

Task Manager - Startup tab Close Task Manager. On the Startup tab of System Configuration, select OK. When you restart the computer, it's in a clean boot environment. Follow troubleshooting steps to install, uninstall, or run your application. Your computer might temporarily lose some functionality while in a clean boot environment. Reset the computer to start normally after clean boot troubleshooting and resume functionality.

I also had this issue with Steam. As you said, there are a few workarounds, but let's find a solution.

Before trying any steps, make sure Steam is not running. You may need to finish the processes with Task Manager.

Now, let's remove the cache. Open your Steam Installation Directory (Most likely C:/Program Files (x86)/Steam/) and delete the entire appcache folder.

If that did not work, let's reinstall Steam. Be aware that if you want to keep your games installed, you must copy the content of C:/Program Files (x86)/Steam/steamapps/common/ to a safe place and move them back after Steam is successfully reinstalled (read more about it here). Now, run the uninstall.exe file located inside your Steam Installation Directory (Again, most likely C:/Program Files (x86)/Steam/). Next step, download the installer from the official website and run it.

If the issue persists after reinstalling Steam, it might be an OS problem. I'm aware that this issue is happening on multiple accounts/machines/OSes, but let's give these steps a try:

Assuming you're running Windows: open the Command Prompt as Administrator. Click here to learn how. On the new CMD window, run the command sfc /scannow. It may take some time to complete, but when it is done, run DISM.exe /Online /Cleanup-image /Restorehealth. Make sure you have a working internet connection. Also, check if there are any available updates on Windows Update. You may need to restart your device.

If none of the above worked: Go to Your Steam Installation Directory and rename the file ClientRegistry.blob to ClientRegistryOld.blob.

Still having issues? Go to Your Steam Installation Directory and locate steamerrorreporter.exe. Run that application and check if Steam is properly starting.

Please, let me know how it goes.

Anytime you have trouble with STEAM you need to make sure to clear the app, then you clear cache and restart you computer. Hope this helps!