I got PCRE up and running with minimal hassle. There are binary versions available for most platforms.

Although its a C library, there are C++ wrappers available, most notably PCRE++. There seems to be a search-replace feature in PCRE++ as well.

More to update when I have abit more time. Today I travel to Münich. Hope to get some programming done on the train.