Рискну предположить, дело в том, что для обработки блока с одним nonce требуется много операций хеширования. SHA-256 "ест" по 512 бит за раз, а размер блока около мегабайта. Плюс в BTC считается двухкратный хеш SHA-256(SHA-256(Data)).
Но даже с учётом всего этого цифры не сходятся где-то на 2-3 порядка.
UPD. Нашёл. Помимо nonce, в блок ещё входит timestamp. Его можно менять в довольно больших пределах, не нарушая валидности блока (он должен быть больше, чем медиана времени предыдущих 11 блоков и меньше, чем средне-сетевое время +2 часа). Прогнав весь диапазон nonce и не получив красивого хеша, майнер немного меняет timestamp и прогоняет весь диапазон nonce заново. А потом снова и снова, пока не попадёт.
Весь диапазон валидных timestamp почти 3 часа ~10^4 секунд. Теперь вроде сходится.