I obviously hadn't quite mastered combining positive lookahead and non-greediness (selflessness?) yet. Until now my solution was to use two statements:

    s{\[_(CELL|COLHEAD)_\] (.*)}{<$1>$2</$1>}g;
    s{\s*\[_(CELL|COLHEAD)_\]\s*}{</$1><$1>}g;
[download]

Here it's more complicated because there's several of these tags. It's lamer and slower than yours, so I'll gladly change it, thanks!

Pauses to think for a while... Hm, with that extra twist I just introduced (not fair, I know), maybe the two-step version isn't slower. Lookahead on something it doesn't know yet could get tricky, maybe.

    s,\[_(CELL|COLHEAD)_\]\s*(.*?)\s*?(?=\[_\1_\]|$),<$1>$2</$1>,g;

But it seems to work fine, and I don't think I care about speed anyway.