Hi,
I've been struggling with the same problem on my netbook (1024x600) and fixed it in the following manner.
xrandr allows you to scale your display (display more (or less) pixels than the native resolution of your screen). So by scaling a 1024x600 display by a factor of 1.28, you get 1311x768, which makes the game fit nicely.
To do this, copy the following into a file named run.sh in the same directory as Machinarium
#!/bin/bash
xrandr --output `xrandr | grep ' connected' | awk '{print $1}'` --scale 1.28x1.28
./Machinarium
xrandr --output `xrandr | grep ' connected' | awk '{print $1}'` --scale 1x1
Make the file executable (chmod +x ./run.sh) and start Machinarium using this file from now on.
Greetings,
Erwin