Along the same lines but going the OOP-y route would be to hide the differing behavior behind a method (similar to the idea behind the replacing the conditional with polymorphism refactoring).

Update: although after actually reading the code in detail (Wall of Text crits you for 195202. You die. :) I see why you've discounted dispatch tables (and for similar reasons my original make-it-a-method wouldn't be a great idea either since there's not a clear hierarchy). I almost want to say that this makes me want to look for something more along the lines of a state machine with separate subs implementing the different branches, but then again I'm drawing a blank on an immediate way to implement it. Not that a state machine would decrease the checks and conditionals, just that it might help break up the flow with more meaningful names (e.g. start with check_for_atail_and_ntail which either handles it or punts to check_for_noatail_with_ntail). Hrmmm . . .