If the above Beautify method is being called for an XmlDocument that already contains an XmlProcessingInstruction child node the following exception is thrown:
Cannot write XML declaration.
  WriteStartDocument method has already
  written it.
This is my modified version of the original one to get rid of the exception:
private static string beautify(
    XmlDocument doc)
{
    var sb = new StringBuilder();
    var settings =
        new XmlWriterSettings
            {
                Indent = true,
                IndentChars = @"    ",
                NewLineChars = Environment.NewLine,
                NewLineHandling = NewLineHandling.Replace,
            };
    using (var writer = XmlWriter.Create(sb, settings))
    {
        if (doc.ChildNodes[0] is XmlProcessingInstruction)
        {
            doc.RemoveChild(doc.ChildNodes[0]);
        }
        doc.Save(writer);
        return sb.ToString();
    }
}
It works for me now, probably you would need to scan all child nodes for the XmlProcessingInstruction node, not just the first one?
Update April 2015:
Since I had another case where the encoding was wrong, I searched for how to enforce UTF-8 without BOM. I found this blog post and created a function based on it:
private static string beautify(string xml)
{
    var doc = new XmlDocument();
    doc.LoadXml(xml);
    var settings = new XmlWriterSettings
    {
        Indent = true,
        IndentChars = "\t",
        NewLineChars = Environment.NewLine,
        NewLineHandling = NewLineHandling.Replace,
        Encoding = new UTF8Encoding(false)
    };
    using (var ms = new MemoryStream())
    using (var writer = XmlWriter.Create(ms, settings))
    {
        doc.Save(writer);
        var xmlString = Encoding.UTF8.GetString(ms.ToArray());
        return xmlString;
    }
}