Grazie per tutti i suggerimenti.
Ho provato alcune cose oggi e, con le cose che stiamo cercando di fare, ho optato per la soluzione più semplice in cui non devo scaricare nessun'altra libreria di terze parti. Alla fine, ho #include
Boost.Regex è molto buono ed è destinato a diventare parte dello standard C++0x (è già in TR1).
Personalmente, trovo che Boost.Xpressive sia molto più piacevole con cui lavorare. È una libreria di sole intestazioni e ha alcune funzioni interessanti come le espressioni regolari statiche (regexe compilate in fase di compilazione).
Aggiornamento: Se stai usando un compilatore conforme a C++11 (gcc 4.8 NON lo è!), usa std::regex a meno che tu non abbia una buona ragione per usare qualcos'altro.