Для немного другого подхода, возможно, стоит попробовать DirectoryInfo , внутренне он может использовать другой подход, чем Directory.Exists ():
DirectoryInfo di = new DirectoryInfo(yourPath);
if(di.Exists())
{
...
}
Но будьте внимательны, конструктор в некоторых случаях вызывает исключения.
Поскольку это не статический класс, он может работать еще хуже, но я думаю, стоит попробовать.