Ну во-первых, твой стек не lock-free, а lock-based. В функции Pop() у тебя записано не что иное, как spin-lock. Т.е. используются мелко-гранулярные спинлоки на каждый элемент. Это будет очевидно, если переписать функцию как:

    public Int32 Pop()
    {
        while (count > 1)
        {
            Int32 head1;
            Int32 next1;

            // spin-lock acquire
            for (;;)
            {
              #define LOCKED -1
              head1 = head;
              next1 = Interlocked.Exchange(ref array[head1].Next, LOCKED);
              if (next1 != LOCKED)
                break;
            }

            if (Interlocked.CompareExchange(ref head, next1, head1) == head1)
            {
                Interlocked.Decrement(ref count);
                return head1;
            }

            // spin-lock release
            Interlocked.Exchange(ref array[head1].Next, next1);
        }

        return -1;
    }

При этом спинлок реализован, мягко-говоря, не особо хорошо. Хороший спинлок должен вызывать инстркцию PAUSE (или аналог) на каждой итерации, плюс переключаться на пассивное ожидание при очень большом кол-ве неудач захвата. Иначе это может очень негативно сказываться на производительности.
Во-вторых, я сомневаюсь, что он будет быстрее стека, защищенного спинлоком. Почему? Потому что при использовании спинлока функции Push()/Pop() будут выполнять по 1 атомарной RMW операции. В твоём же стеке функция Pop() выполняет 3, а функиця Push() — 2. Т.е. Грубо говоря твой стек в 2.5 раза медленнее спинлока.
В принципе, твоему стеку можно провести небольшую липосакцию. Известно, что lock-free стек реализуется с 1 атомарной RMW операцией в Push() и Pop().
Первое, можно избавиться от переменной count. Для этого необходимо положить в Next последнего узла -2, тогда поток, поток снимающий элемент со стека, будет понимать, что элемент временно заблокирован (Next=-1) или стек пустой (Next=-2).
Далее, в функции Pop() можно разблокировать элемент с помощью обычного сохранения, а не Interlocked.Exchange (точно так же как элемент разблокируется в функции Push() перед помещением в стек).

В-третьих, в алгоритме содержится гонка, которая может приводить к падениям, зависаниям или выдаче некорректных результатов. В целом, это та же ABA проблема.
Вот конкретный сценарий:
1.Поток 0 считывает head=0 в Pop().
2.Поток 1 считывает head=0 в Pop().
3.Поток 0 снимает элемент 0 со стека, теперь head=1.
4.Поток 0 начинает добавлять элемент 0 в стек.
5.Поток 0 считывает head=1, и записывает 1 в поле Next элемента 0.
6.Поток 1 делает Exchange для поля Next элемента 0. Он записывает туда -1 и получает значение 1.
7.Поток 2 снимает элемент 1 со стека, теперь head=2.
8.Поток 0 делает неудачный CompareExchange, перечитывает head=2, и записывает 2 в поле Next элемента 0.
9.Поток 0 делает удачный CompareExchange (добавялет элемент 0 в стек), теперь head=0.
10. Поток 1 делает удачный CompareExchange (снимает элемент 0 со стека), теперь head=1, однако должен быть 2, т.к. Поле Next элемента 0 было равно 2, когда он добавлялся в стек.
11. Теперь любой поток (для определенности 0) снимает элемент 1 со стека. И получаем, что поток 0 и поток 2 одновременно получают элемент 1 из стека. Это может привести к любым негативным последствиям. В хорошем случае программа сразу упадёт. В случае похуже один или несколько потоков зависнут. В самом плохом случае программа выдаст некорректные результаты (переведёт деньги на некорректный счёт).

Добро пожаловать в мир lock-free

Я бы рекомендовал просто реализовать классический lock-free стек. Тут есть 2 варианта. Первый, динамически выделять на каждый элемент дополнительный вспомогательный элемент узла. Второй — добавить т.н. IBM ABA-tag рядом с каждым полем Next. Любой из этих вариантов будет быстрее (1 atomic RMW на операцию), давать гарантии lock-free, и главное будет надёжно работать.

Верификация алгоритмов синхронизации — это экстремально сложная задача. Если ситуация кажется простой, скорее всего ты просто что-то упускаешь. Советую не пренебрегать чтением pdf'ок по теме, или просто использовать готовые библиотеки; хотя и там и там бывают ошибки (особенно в самопальных библиотеках, которых в интернете разводится всё больше и больше). Или просто заказать необходимые компоненты у экспертов.