Things got even more interesting - I tested the game on my notebook as well and it worked out-of-the-box with neither Steam nor the game being installed on the C: drive.

The only significant difference between both machines that I can think of is the storage. The desktop system is running Steam from a Win8 storage space while the notebook has it running on a regular drive.
The OP is running Win 7 though, so Storage Spaces are an unlikely cause.

Anyway, if I happen to find anything else, I'll add another note so you guys can look into this issue.

Can confirm the problem as well as the solution. Game only runs if installed using a Steam installation on C: drive.

Just installing the game in a C: drive library via a G: drive Steam installation did not help.