I've also had this problem with Poly Bridge 2. I tried out the Windows version with Proton, but it didn't work for me, so I deleted it and got a refund.
A few weeks later, the Linux version came out, so I bought it again. However Steam kept downloading the Windows version, then tried to play the Linux version, resulting in the "missing executable" error message. It even said it was going to downoad 430 MB, but the download manager said it was only downloading 333 MB.
The same fix worked for me: checking the "Force use of a specific SteamPlay compatibility tool", and then leaving the default of "Steam Linux Runtime". It then downloaded the correct version, which worked.
I experienced this too recently, this thread has reports from several users hitting this issue switching from Proton to a newly released native build:
https://steamcommunity.com/app/1369320/eventcomments/3003298578158264408
Nothing extracted yet.
Your system information
Please describe your issue in as much detail as possible:
On March 26 the game Unbound: Worlds Apart Prologue was released for Windows. I tried to play the game with Proton, but it only worked until the first cutscene.
On April 10 the developer released a native Linux build. However the Steam client continued to use the Win64 depot of the game. Clicking the Play button resulted in a "missing executable" error message. The manifest file continued to list the ID of the Win64 depot (1234811) in the
MountedDepotssection.Uninstalling the game, removing it from my account and re-installing it did not help. I finally succeeded to convince the Steam client to switch to the correct depot (1234813) by temporarily checking the "Force use of a specific SteamPlay compatibility tool" option in the game attributes.
Steps for reproducing this issue:
Can't be easily reproduced because it depends on a Linux version being released for an already installed game.