I like this idea but I'm having trouble get a 2 pass solution to work nicely...

I don't understand your difficulty...

Sorry, I had to leave work about the time of my last message yesterday (well, actually 10 minutes _before_ my last message!), but didn't want to disappear without writing back. And I'm not good at coding under stress (and not fantastic the rest of the time either!).

Anyway, thanks for taking the time to write out the code there. Strangely enough, I tried it this morning, and the memory usage of this is actually higher than the original, at least as Linux measures it! I'm processing a 65MB test file - after the first pass the script is consuming 100MB of memory, and after the sort then 200MB!
With this test file, @unlock_lines ends up with 800000 entries, but still I was surprised. My original script used (RSS & VSZ) 160MB, and using a hash to store the file in memory (so as to properly free the deleted lines) brings it down to 110MB...

Thanks also for '$.' - I didn't know about that one!