Well, after several efforts fizzled over the years, TASVideos finally has a Lemmings submission! Will it be published? You be the judge!
This is SNES 'Mayhem+Sunsoft' Lemmings, completed in 1:03:04.45 (227067 frames). I recorded it using "Snes9X v1.43+ v13 (lua 0.05) for Windows" with the default settings.

Goals:

  1. Completes the game without passwords, starting at 'Mayhem'
  2. As fast as possible, with some lag allowed as a speed-entertainment trade-off
These goals were revised by popular request after the initial submission, with the addition of the 5 Sunsoft levels -- specially designed for this port to be uniquely challenging.
Many believe that the ideal Lemmings run would complete all 120 levels. However, with each level taking, say, 1.5 minutes, that's 3 hours, and many of the levels repeat with subtle differences to increase difficulty as the game progresses. Finally, the game permits starting at 'Mayhem' without a password, so in that sense the game is completed at the highest difficulty level, rather than being incomplete. The result is, I hope, a movie of digestible length, minimal repetition, and a fairly high density of interesting strategies peppered with the occasional unnecessary exploding lemming.
Goal #2 became obvious when I started the run; the shortest possible time requires minimal lag, which requires having no lemmings at all on the screen for large stretches. Not good for entertainment. Thus, I try to minimize 'screen time' for the large blocks of lemmings that cause lag, but allow it if that's where all the action is. In the end, most levels have some of this lag, but there are only a few where it's really noticeable.

TAS'ing Lemmings

My first puzzle game; each level is trivial to beat, of course, since it's a TAS, but planning the use of each lemming type to get as fast as possible is quite a rich challenge. The timing for getting lemmings at the right place at the right time was often quite laborious to optimize, as frequently a bomber might have to be started as long as a minute before they'll actually reach the relevant obstacle.

General Tricks:

Packing: Trapping a bunch of lemmings in as tight a space as possible can often save time because when they're released, there is less time between when the 1st and last lemming clears an obstacle. This is used in most levels.
Bridge stretching: Using multiple builders in rapid succession is used in several places to rapidly clear horizontal spans, i.e. pits.
Going through steel/wrong way arrows: * Bash: Bashing just as a lemming turns around will usually take a small chunk out. When there's only a few pixels of steel remaining, you can just bash through forwards. * Dig: By first building a bridge and digging down from it, it is possible to dig various distances into steel. * Bomb: Bomber lemmings can damage steel if the detonation occurs a sufficient distance away.
Building out of mid-air: when the wall is blown out from under a climber, there are a few frames before he falls in which he can be made a builder; useful in a few levels.
Timely release: Used constantly; one or more lemmings is somehow released at the perfect time so that it reaches an obstacle just as another lemming clears the way. Often used multiple times in a given level.
Use a stopper to force lemmings deep into a wall: If two lemmings are almost on top of each other, turning one into a stopper just as they hit a wall can force the other lemming to walk into the wall, where he can be blown up to take a bigger chunk out than ordinarily possible.

Mayhem Level Comments:

1: Most notable is building up to just under a ledge to reduce the number of building slabs required to get up the large cliffs. I also dig through steel after the 1st cliff in a way that saves a builder and provides a useful timely release. This level was redone at the end to save about 45 seconds in lag and building time.
2: Broken collision detection is on display here. You're not supposed to be able to get the lemmings up past the fire (you're meant to dig through from beneath the exit), but there's just room to avoid getting toasted. Also redone at the end to save about 40s by bridge-stretching and lag reduction.
3-4: Nothing noteworthy.
5: One of my favorite levels in terms of ridiculously precise timing.
6: Turning around on steel by building then digging is used for the 1st time here. GameFAQs said going right is impossible for this level. :)
7: This level is destroyed by digging on just the right frame. This level was meant to be beaten by climbing each pillar and digging all the way down through it.
8: I discovered the tiny lip that the lemmings drop down onto purely by accident, but it saves major time here!
9: Having the two lemmings build toward each other looks bizarre, but serves 2 functions: turning a lemming around so he can build over the obstacle at left (stoppers not available), and providing a path for the lemmings to follow.
10: Yeah, you can go through the friggin' ceiling.
11: Rapid fire diggers!
12: It would've been soooo nice if one could get through the steel right to the exit. Alas...
13: This level is meant to require synchronized action of the 2 lemmings. However, with some precision maneuvers (whose sole purpose is to delay the trailing lemming while the lead lemming builds a bridge), a much faster solution is possible.
14: One of 2 major disappointments in this run. It is VERY close, but just impossible to use diggers/bombers to tunnel under the bowl. Argh!
15: The first multiple entry-point level; TAS's advantages on display, but nothing really to note.
16: Nothing noteworthy.
17: This route is possible because the miner's swing takes out some material above the lemming's head, allowing me to mine upward into the ceiling. One of many levels where there are exactly enough builders/etc to make a strategy work, as if by design...
18: 4 entry points...I think it's safe to say this couldn't be done unassisted...
19: I use a bizarre combo of builders/bomber at the beginning to turn a lemming around w/o a stopper. The bottom lemming ends up building into the upper builder, which turns him around w/o having to walk all the way left.
20: The 2nd major disappointment; despite all the crazy stuff I tried, there just doesn't seem to be a way to beat this level without mining one lemming all the way down and having to wait for him.
21: Annoying "make every lemming a floater" level; a little geometric puzzling gave a somewhat faster route than the obvious one. Also, each lemming is made a floater at a specific time to group them all together, which allows for tighter packing.
22: One of the most fun & difficult levels to make.
23: One of the toughest things to plan in this game is bridge stretching late in a level because it requires the timely release of many lemmings a precise distance apart, as opposed to one big pack of lemmings. All the bizarre builder/stopper stuff at the start is oriented toward making that happen.
24: Trivial.
25: This level is toasted by digging through steel and using bridge stretching. The intended solution is difficult to describe, but involves sending one lemming way ahead, having him turn around and build back to the start.
26: The most difficult level to make due to the difficulty of timing a very limited number of bombers.
27: Two diggers are made into bashers in opposite directions to pack the trailing lemmings for a timely release.
28: I don't know what to say. I went right through SOLID STEEL.
29: If the bridge at the start of this level needed to be one pixel wider it would be impossible to build left at the start; again, as if the designers planned it that way.
30: The grand finale! Tough to synchronize the two sides, but nothing in the way of new tricks/strategies.

Sunsoft Level Comments

1: All about timing the bombers. Setting the release rate above 78 will not make the 4th lemming appear any faster.
2: The limiting factor on this level are the last lemmings from the left entrance. Blowing up the 1st digger lemming lets them start to escape much faster. It may be hard to understand what is going on in this level; basically successive diggers are used to make a staircase for the other lemmings to climb; since the staircase is digging into the ground, though, new diggers need to be added at the right side until all the lemmings are past it, or they'd hit the wall and turn around.
3: Far and away the most difficult level to TAS. The strategy is actually not too different from what the designers intended but MUCH faster because so much is done simultaneously. If the lemmings in the 18 cells don't dig down their individual little icicles, they'll splat. Getting 1 cell per lemming, fast, without running out of diggers, and then packing them while still building the path ahead, was a huge challenge.
4: The intended solution for this level is quite elaborate and involves building ladders amongst the 4 blocks beneath and left of the entrance. My solution is quite un-elaborate, and hinges on a technique for having one builder force another to turn around without using a stopper.
5: Careful design and ruthless resource limitations very nearly forced this level to be solved as intended. What saved it is a bug where bashing just as a lemming hits a wall and turns around takes out a divot *behind* the basher. I use this technique with the first lemming to create a divot in the one-way wall. Without this divot, when the climbers reach this wall, they'd climb up and keep going right, to their deaths; the resulting solution would have been at least a minute longer.

Thanks

Thanks to the dozen or so people who discussed this game in its various platforms and posted WIP's over the years. Also, my wife and baby for letting me TAS while also working 80 hour weeks.

Future Improvements

The most likely levels for improvement are the "great adventure" levels where there's many lemmings, lots of extra builders/etc, and wide/varied terrain to cross. There's so many different ways to beat them, I can't say I found the absolute fastest. Of course, any time a new technique is found, there is also the potential to save large amounts of time.

adelikat: replaced submission file at author's request. New file has 5 additional levels.
Bisqwit: Accepting the submission for publication, and starting to make an AVI.