The night I stayed in the albergue in O'Cebreiro, it did get full, and they rigidly applied 'priority' there. The cyclists who wanted to stay had to wait until quite late -maybe it was even after 8pm- to see if there was room. A couple of groups, including teenagers and adults, arrived by taxi to begin in O'Cebreiro. They were lowest in priority, and one of these family groups ended up sleeping outside the albergue, on what was a very chilly evening on a mountaintop. However, if you have walked 5km, you have walked at least something, so as sil says, it might then depend on the hospitalero.
Margaret