I have the solution!
The credit actually goes to my boss who advised, that in his experience many of the networking/connections issues he had in the past were related to IPv6, so he just ended up getting rid of that completely in his setup. Indeed a few years ago I was having issues uploading to our company FTP server and the solution was disabling IPv6 in Windows. But, obviously, that only applies to my laptop, not the Tesla app running on my phone.
So, I logged into the admin page of my router, completely disabled IPv6, and this has fully resolved the issue. I am able to connect to the car even after 10-12 hours of deep sleep state every single time.
IPv6 does have some benefits, which also pose some security risks, as it enables direct access from the outside to specific devices to the gadgets connected to your network. So depending on your smart home setup, you need to test if disabling messes up something else for you. Also, this wasn't an issue with my previous ISP, so the solution may or may not help you given the networking equipment and protocols your ISP may use.
But, for me, this has completely solved the issue with zero drawbacks, and I feel like it has also made my network a little more secure, so I wanted to share it, in case it helps others.