Just another black box day. I had to move an EC2 instance to a different subnet, so I created an AMI out of it and launch it on a different subnet. Everything went well and it has no issue reaching the internet, but apparently not everything went well.
The AWS agents such as SSM agent and CodeDeploy agent in the instance stop working. After checking the logs, they can't access the EC2 metadata. Since this is a Windows Server 2019 instance, it also shows that it is not activated, which is strange.
On the following article, I found out that my issue was due to the "Gateway Address doesn't match that of the current subnet".
Running the suggested command fixed the issue:
Import-Module c:\ProgramData\Amazon\EC2-Windows\Launch\Module\Ec2Launch.psm1 ; Add-Routes