This functionality was introduced in Emacs 23.1. In earlier versions, C-l
behaved just like you describe: it always recenters the buffer, never cycles between top and bottom.
From the "Emacs 22 Antinews" section of the Emacs 23 manual:
For those users who live backwards in time, here is information about downgrading to Emacs version 22.3.
...
C-l
now runs recenter instead of recenter-top-bottom. This always sets the current line at the center of the window, instead of cycling through the center, top, and bottom of the window on successive invocations. This lets you type C-l C-l C-l C-l
to be absolutely sure that you have recentered the line.