Так происходит, потому что у типа object сравнение на равенство определено по ссылке. Очевидно, в качестве ключа для Dictionary нужно использовать не Object, а конкретный тип, для которого реализовано сравнение по значению. Либо использовать нестандартный Comparer.

"Что не так?"

Нужно не наследовать от Dictionary, а реализовать интерфейс IEqualityComparer (пример есть на странице его документации), и передать его объект в конструктор Dictionary. Либо как сказали выше, создать свой объект с переопределенными GetHashCode() и Equals(). Т.е. в конечном счете все сводится к реализации своих версии этих двух методов.

"Сравнение по хэшам я сделал только потому, что не знаю как ещё сравнить объекты на эквивалентность"

В вашем случае - просто в цикле сравнение всех элементов массива, и возврат false на первом отличии. А GetHashCode надо реализовать так, чтобы он возвращал одно и то же для одинаковых массивов, но при этом не слишком долго считался (в самом простом случае можно взять сумму или XOR от N первых элементов массива). 

Передать его аргументом конструктора

 New Dictionary(Of Object, Long)(MyEqualityComparer)