"Sever not responding" - The case of a very picky server

Our server seems to have a mind of it’s own.

Yesterday we tried to launch some new servers (3 gmod, 1 tf2). However, people started reporting that the servers were not responding. This struck me as odd, why would some people be unable to connect to the server while others can?

Well, some trial and error later, and it turns out that the servers are only visible when you’ve connected to another service on the machine (and very rarely otherwise). Doesn’t matter which service you connect to, could be teamspeak, web, even remote desktop works.

We’ve went through all the normal troubleshooting steps, and at this point we’re stumped. It’s going to be something simple that we’ve overlooked and will feel very stupid about, or it’ll be something so ridiculous we’d have no chance of guessing.

There are no notable errors in the server’s consoles. sv_lan is definitely 0. Firewall is correctly configured.
I even checked the ports while the server was not responding, everything is as expected.

Has anyone run in to this issue before? And if so, how was it resolved?