Somewhat belated reply ;-)

Even if you don't use the call stack, I think that the regex engine is probably the wrong choice - it's just not made to be used that way easily (as you've found out :-)

Implementing backtracking isn't really that hard. All you really need is a stack. I'd start there if it was me.