It seems that Blender randomly selects when to extrude on a locked axis or projected from the viewport. How do I extrude so that it locks on the axis the vertices are facing?
It's a real pity, but Blender is indeed broken like that. It does not do what it says. If you choose to Extrude and move on normals it works only if you have faces selected and with edges and vertices it does not work. This could be considered to be a bug, since the functionality does not work as intended or as it's label suggests at least. Luckily, it is not a huge inconvenience since it can be fixed very easily - you can just hit Enter without moving the vertices when extruded and then use Shrink/Flatten(alt+s) to move them in the direction of their normals:
You can also use the functionality of the transform operators to move them as you wish after they are extruded:
Edit: who could have thought?.. - it is broken here as well - you can see in my example gif that the vertex normals change when they are extruded with regular e. Well, if you use Extrude Only Vertices from the Space menu, it seems to work. This is a complete mess when you think about it... I am surprised they managed to leave it like that.