I did some more testing and managed to eliminate SQL as a possible cause. I created a new gMSA account, registered SQL SPN and used it to run SQL service and SQL agent on a test server. Now when I restricted both gMSA and the server account to AES256, it still worked. So it seems it's something with the old SQL service account which has been around probably since Windows 2000, but it's not the only one from that time, but it's the only one causing this issue.
Replacing this account across the domain is a bit tricky as it has 1000+ SPNs registered, configured Kerberos delegation for dozens of apps etc, so preferred way would be to fix it at this stage.
Is there something in the account's setting that could prevent it from using AES for Kerberos encryption?
Thanks