Herlihy's result, indeed the whole paper, is about wait-free synchronization. Corollary 1 states that there is no wait-free two-process consensus protocols using atomic registers. Wait-free is defined informally at the beginning of the introduction, and defined formally in the automata model in §2.3.
Dekker's algorithm is not wait-free. The busy-wait loop to enter the critical section is a wait in the sense of Herlihy. It's possible to have P0 set its
wants_to_enter flag, then P1 sets its own, then P0 sees that P1 wants to enter and one of the processes busy-waits (depending on the
Think of wait-free as “must work even with a hostile scheduler”, i.e. with a scheduler that always switches between processes at the most inconvenient time. Dekker's algorithm requires a scheduler that's at least weakly fair, i.e. guaranteeing that if a process is schedulable then it's eventually scheduled (as opposed to being locked in an order of execution that causes a livelock, such as never exiting the busy-wait loop). Wait-free algorithms complete in finite time with any scheduler that doesn't completely lock up the system if there's work to do (no fairness requirement).
Busy-wait loops require the scheduler to be preemptive (otherwise the loop runs forever). In practice a busy-wait loop would be written with a yield call, and even non-preemptive schedulers try to avoid immediately re-scheduling a process that just yielded. But even with a preemptive scheduler, busy-wait is generally bad: if nothing else it uses up CPU time and electricity. A case where Dekker's algorithm doesn't work at all is if the two processed have different priorities and the scheduler never schedules the process that would enter the loop because the busy-waiting process has a higher priority.
A naive solution to avoid waiting is to put in a time delay. It isn't a good solution because in practice it means an additional useless delay when there is contention on the mutex, and in theory the delay isn't enough since the scheduler could take that long to make its decision and so end up scheduling the busy-wait loop only anyway. A good solution avoid busy-wait altogether is to add a primitive that lets a process block until some shared variable is modified; with such a primitive, I think it's easy to achieve an infinite consensus number.
It is instructive to contrast Dekker's algorithm with a wait-free consensus solution, such as the one Herlihy gives for two processes (fig. 7).
prefer[P] := input
if RMW(r,f) = v
then return prefer[P]
else return prefer[Q]
RMW is a primitive operation with a consensus number of at least 2, for example test-and-set. There's no busy-wait in the consensus protocol itself: both processes run pretty much instantly, without ever waiting for the other one. In a real scenario, the processes that doesn't acquire the mutex may well wait for it; but the process that does acquire the lock isn't stopped, and in practical terms that means at least an expected performance gain both when there is contention and when there isn't.