Obviously when I said I 'tried' it was through 'forcing' because the game does not have any internal anti-aliasing options. There is no other way to have anti-aliasing in these older games as far as I know.
I also said I was using an ATI graphics card because I know Nvidia and ATI cards behave differently (even between different models or drivers) and maybe someone with a Nvidia card could comment on whether they had any success with 'forcing' anti-aliasing.
Maybe anti-aliasing don't work for games played in a window (fsaa being abbreviation for full-screen anti-aliasing). But I don't usually play games in a window or force AA so I wouldn't know.
I also tried 'forcing' anti-aliasing full-screen as well with no difference. That was both official Lemming Revolution versions and also with the awesome custom hack patch.
Oh yeah, when 'forcing' anti-aliasing I noticed all the ingame videos wouldn't play properly either.