OK, it really seems to be due to the variable order. If I change the code to
handle the first abstraction in the same way as the later ones, by
unconditionally setting "is_first = false;" before creating the
VariableOrderFinder, the performance is also terrible with just one abstraction:

./downward-1 < output --search 'astar(mas(max_states=1000,count=1))'
takes 1056.14 sec

So for whatever reason the default, level-based variable order works much better
here than the random ones that ignore variables. Interesting.

So there's nothing to fix here, but maybe it's worth investigating variable
orders a bit more in the future.

Still seems to be the case in the current code:

./downward-1 < output --search 'astar(mas(max_states=1000,count=1))'
takes 32.16 sec

./downward-1 < output --search 'astar(mas(max_states=1000,count=2))'
takes 1041.84 sec

By "pre-processing", of course I mean heuristic construction.

If I run merge-and-shrink on the attached pre file in r3753, preprocessing takes
8.47 seconds with options "oa1000" and 600.65 seconds with options "oa1000A3".
It's not clear why it should become that much slower -- I'd expect more like a
linear slowdown, although of course the alternative abstractions might have
worse variable orders. Still... maybe something fishy here, bad cache behaviour
or whatever?

(This was tested on alfons. The input is based on a problem received by Jörg;
sources for that attached. I needed to disable invariant synthesis because the
translator introduce conditional effects otherwise.)