DNS resolution issues when attempting to connect to login.microsoftonline.com

Just as an FYI for anyone that may be looking into any similar issue, we have figured out exactly what is happening.

As suspected, the routers or Residential Gateways in question were not listening to TCP port 53 on their Default Gateway Address, which is as good as blocking it on their.

It appears that several brands have flawed firmware.

The only option is to either configure custom DNS settings to be served to the clients on the router, search for a firmware updated that fixes this issue. We opened a few tickets with some of our hardware vendors to have them investigate and fix the issue. One of those vendors is working on updating their firmware and will likely push a firmware upgrade globally in the months to come. Luckily their type of hardware allow for this upgrade to easily be pushed to all devices at once.

If you are experiencing this issue, look for firmware upgrades, if they exist, open a ticket with the vendor's customer service if you can, customize your router settings to serve a few custom DNS servers, or get a new router if all else fails.