Recently I was searching the forums for a way to do search and replace.  In the end I wrote this code - hopefully it will be useful for some people.   

This does S&R directly on the DB.  It requires you create a dbml file with the tables:

cmsDocument
cmsPropertyData
cmsContentXml
umbracoNode

LinqBaseUmbraco is just a wrapper to manage the Linq data context object. 

The code will update all references in the property data, the page node titles and url names, and finally the cached xml.  It will require a "Republish Entire Site" afterwards to update the local cache.  It will only apply the search and replace to the current version of the document, and won't require each page to be republished (it was a requirement for me to not update the last-update-date during the S&R).  

Finally, it is case sensitive and should only be used with alphanumeric chars and spaces (this is because the url encoding can only handle this).

string search = "string1";
string replace = "string2";

List<int> nodeIds = new List<int>();

LinqBaseUmbraco lb = new LinqBaseUmbraco();

// replace items in property data table

var pq =
    from p in lb.CurrentDB.cmsPropertyDatas
    where
        (p.dataNtext != null && p.dataNtext.Contains(search)) ||
        (p.dataNvarchar != null && p.dataNvarchar.Contains(search))
    select p;

foreach(cmsPropertyData cpd in pq)
{
    if (isCurrentVersion(cpd.contentNodeId, cpd.versionId.Value))
    {
        cpd.dataNtext = cpd.dataNtext != null ? cpd.dataNtext.Replace(search, replace) : null;
        cpd.dataNvarchar = cpd.dataNvarchar != null ? cpd.dataNvarchar.Replace(search, replace) : null;

        if (!nodeIds.Contains(cpd.contentNodeId))
        {
            nodeIds.Add(cpd.contentNodeId);
        }
    }
}


// replace items in document titles 

var dq =
    from d in lb.CurrentDB.cmsDocuments
    where d.text != null && d.text.Contains(search)
    select d;

foreach (cmsDocument cd in dq)
{
    if (isCurrentVersion(cd.nodeId, cd.versionId))
    {
        cd.text = cd.text != null ? cd.text.Replace(search, replace) : null;

        if (!nodeIds.Contains(cd.nodeId))
        {
            nodeIds.Add(cd.nodeId);
        }
    }
}

// replace items in umbraco node tree

var nq =
    from n in lb.CurrentDB.umbracoNodes
    where nodeIds.Contains(n.id)
    select n;

foreach (umbracoNode un in nq)
{
    un.text = un.text.Replace(search, replace);
}


// replace items in cached xml content and urls

var xq = 
    from x in lb.CurrentDB.cmsContentXmls
    where nodeIds.Contains(x.nodeId)
    select x;

foreach (cmsContentXml x in xq)
{
    XmlDocument xd = new XmlDocument();
    xd.LoadXml(x.xml);

    XmlNode rootNode = xd.SelectSingleNode("//node");
    if (rootNode.Attributes["nodeName"] != null)
    {
        rootNode.Attributes["nodeName"].Value = rootNode.Attributes["nodeName"].Value.Replace(search, replace);
    }

    if (rootNode.Attributes["urlName"] != null)
    {
        string urlSearch = search.Replace(" ", "-");
        string urlReplace = replace.Replace(" ", "-");
        rootNode.Attributes["urlName"].Value = rootNode.Attributes["urlName"].Value.Replace(urlSearch, urlReplace);
    }

    XmlNodeList nodeList = xd.SelectNodes("//data");
    foreach (XmlNode xn in nodeList)
    {
        if (xn.InnerText.Contains(search))
        {
            if(xn.FirstChild is XmlCDataSection)
            {
                XmlCDataSection xcds = xn.FirstChild as XmlCDataSection;
                xcds.InnerText = xn.InnerText.Replace(search, replace);
            }
            else
            {
        xn.InnerText = xn.InnerText.Replace(search, replace);
            }
        }
    }

    x.xml = xd.OuterXml;
}

lb.CurrentDB.SubmitChanges();