Hey I remember that Lemmings was a pretty old game. Generally Axim uses double-pixelling to automatically allow the program to fit to the screen size.
I can think of two options:
1. Use a registry key to change resolution. But it messes up everything else. Not recommended.
2. Give this a try:
Nyditot. It creates a virtual display resizable to any size/orientation.