Actually it was a coincidence that I started looking at this at all - I was originally digging around in the Amiga version of Lemmings to try to extract the sounds because several of the Windows ones sound sped up in comparison. After I stumbled upon this thread it intrigued me enough to have a look into the compression of the levels.
Anyway, what gave me the clue to the compression format was the documentation for XFD which stated that it could decompress ByteKiller compressed files that had had their headers modified or moved to the end of the files. I messed around with the Level000 file from the Lemmings hard drive installation provided by Mindless, first decompressing it with XFD and then attempting to recompress it and end up with exactly the same file I started with. After some time playing around with it I managed to figure out the required method to do this. I then just applied the same technique to a custom, uncompressed level pack (saved in .lvl format in Lemmix), plugged it into the Lemmings installation and, hey presto, it worked.
Stand by for a full description of how to compress the levels.