Hello everyone, I am praising the Lord rn, I got it to work for me! I think they finally listened to our niche group of problem havers (https://status.seaofthieves.com8/10/2)! Or it may have just worked by the countless things I've been trying (and undoubtedly you as well), and so this being the last thing I tried.
What I did was change the potential problematic folder's ("C:\XboxGames\Sea of Thieves\Content\Athena\Binaries\WinGDK", "C:\XboxGames\Sea of Thieves\Content\EasyAntiCheat", "C:\XboxGames\Sea of Thieves\Content\Installers") to not compress to save disk space in properties -> advanced for all these folders (Uncheck "Compress contents to save disk space").
Then I deleted the application having the issue (SoTGame.exe).
Then I verified files through Xbox.
And providentially it worked! YAY! Best feeling! I hope it works and finally. Goodness me.
If you still having trouble (maybe new problem or something), try running through SoTGame and then look at the error it gives and tell support. I was gunna do this as a final resort, then ask for steam key since it wasn't working for peeps on xbox lol.
P.S. I think the issue is specifically with the WinGDK folder if you care and don't wanna uncheck "Compress contents to save disk space" to all of them. This happened to me again, as I was forced to reinstall the game, and I just tested this folder alone and it worked.