cannot generate sspi - None of Solution worked!

I am receiving "cannot generate sspi" error when I try to connect a sql instance remotely. I suspected the issue might be with spn and verified that spn was registered properly on the service account(confirmed the same with AD team as well). Also tried to get the server removed from domain and rejoined. The issue still persists and issue started occurring all of sudden and there were no changes on the server (patching, reboot). Would appreciate if anyone can provide some lead to resolve this issue?