Gracias por todas las sugerencias.
Probé algunas cosas hoy, y con las cosas que estamos tratando de hacer, opté por la solución más simple donde no tengo que descargar ninguna otra biblioteca de terceros. Al final, #incluí
Boost.Regex es muy bueno y está programado para convertirse en parte del estándar C++0x (ya está en TR1).
Personalmente, creo que Boost.Xpressive es mucho más agradable para trabajar. Es una biblioteca de solo encabezado y tiene algunas características interesantes, como expresiones regulares estáticas (regex compiladas en tiempo de compilación).
Actualización: Si usa un compilador compatible con C++ 11 (¡gcc 4.8 NO lo es!), use std::regex a menos que tenga una buena razón para usar otra cosa.