Initial diagnosis was easy – there was no .NET Framework installed. While there is no way to install .NET Framework 3.5 on Windows Thin PC, .NET Framework 4.0 installs just fine.
Next run gave us another clue with
System.IO.FileNotFoundException: Could not load file or assembly 'System.ServiceModel, Version=220.127.116.11, Culture=neutral, PublicKeyToken=b77a5c561934e089' or one of its dependencies. The system cannot find the file specified.
While .NET 4 is backward compatible, Microsoft made intentional decision that it will not run applications made with earlier runtimes. This is not a big issue in Windows 7. There you have 2.0, 3.5 and 4.0 installed side-by-side and each application can pick whatever it needs. However, in Windows Thin PC there is only 2.0 and 4.0. Notice that one version is missing and it was the one I needed.
To make long story short, there is solution that does not involve recompiling. Just add Application Configuration Files (App.config) and put following text into it:
<supportedRuntime version="v4.0" />
<supportedRuntime version="v2.0.50727" />
This will tell application to run on .NET 4 if possible and to fallback to 3.5, 3.0 and 2.0 as a backup solution. This might not be most beautiful solution but it is a solution that works.
P.S. Yes, supportedRuntime cannot distinguish between .NET 2.0, 3.0 and 3.5.