Game can't be installed on Steam Deck, "missing executable"

I have never seen this problem before.

Specifically it was an indie game Storm Boy, works fine when played/installed on Windows. However, on the Steam Deck the install only takes a few seconds (I suspect something wrong happens) and then when you launch I get the following error:

​

Failure

An error occurred while updating Storm Boy (missing executable):

/home/deck/.local/share/Steam/steamapps/common/Storm Boy/StormBoy.exe

​

As the game is ~500 Mb in size and the install finished in a second or so. I've tried to uninstall and reinstall several times, no change. Never observed this behavior previously and I must have played or tested close to 100 games so far.

Any ideas?