How about this? It avoids the exception often thrown by the in-built recursive search (i.e. you get access-denied to a single folder, and your whole search dies), and is lazily evaluated (i.e. it returns results as soon as it finds them, rather than buffering 2000 results). The lazy behaviour lets you build responsive UIs etc, and also works well with LINQ (especially First(), Take(), etc).
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
static class Program { // formatted for vertical space
    static void Main() {
        foreach (string match in Search("c:\\", "*.xml")) {
            Console.WriteLine(match);
        }
    }
    static IEnumerable<string> Search(string root, string searchPattern) {
        Queue<string> dirs = new Queue<string>();
        dirs.Enqueue(root);
        while (dirs.Count > 0) {
            string dir = dirs.Dequeue();
            // files
            string[] paths = null;
            try {
                paths = Directory.GetFiles(dir, searchPattern);
            } catch { } // swallow
            if (paths != null && paths.Length > 0) {
                foreach (string file in paths) {
                    yield return file;
                }
            }
            // sub-directories
            paths = null;
            try {
                paths = Directory.GetDirectories(dir);
            } catch { } // swallow
            if (paths != null && paths.Length > 0) {
                foreach (string subDir in paths) {
                    dirs.Enqueue(subDir);
                }
            }
        }
    }
}