Simplifying exception handling on Enumerators
I would use Linq methods to simplify the code. Also I've extracted 2 methods to simplify the main method. And please rename GetFilesWeAreLookingFor to whatever your find appropriate :).

private static IEnumerable&lt;string&gt; GetFilesWeAreLookingFor(string currentDir)
{
    try
    {
        return Directory.EnumerateFiles(currentDir, "*.exe")
            .Where(fileName =&gt; fileName.IndexOf("unins", 0, StringComparison.CurrentCultureIgnoreCase) == -1);
    }
    catch (UnauthorizedAccessException uae)
    {
        Debug.WriteLine(uae.Message);
    }
    catch (PathTooLongException ptle)
    {
        Debug.WriteLine(ptle.Message);
    }
    return Enumerable.Empty&lt;string&gt;();
}

private IEnumerable&lt;string&gt; GetNestedFiles(string currentDir, int nestedDepth)
{
    try
    {
        return Directory.EnumerateDirectories(currentDir)
            .SelectMany(subDirectory =&gt; SearchSubdirs(subDirectory, nestedDepth));
    }
    catch (UnauthorizedAccessException uae)
    {
        Debug.WriteLine(uae.Message);
    }
    catch (PathTooLongException ptle)
    {
        Debug.WriteLine(ptle.Message);
    }
    return Enumerable.Empty&lt;string&gt;();
}

private IEnumerable&lt;string&gt; SearchSubdirs(string currentDir, int currentDepth)
{
    IEnumerable&lt;string&gt; filesWeAreLookingFor = GetFilesWeAreLookingFor(currentDir);

    if (currentDepth &lt; _maxDepth)
        filesWeAreLookingFor = filesWeAreLookingFor.Concat(GetNestedFiles(currentDir, currentDepth + 1));

    return filesWeAreLookingFor;
}