Why doesn't extruding from some edges make a face while usually it does? The first picture is when I extruded after selecting two vertices and it gave me an additional face, three edges and two vertices as you can see.
But the second picture is when I extruded after selecting (some)two vertices and it gave me no faces and only additional two edges. 

It seems like if I select one already extruded vertex and one that I didn't, the second scenario happens. 
Why? And how do I make a new face in the latter case?
Can you confirm that you select the connected vertices rather than a duplicated one?
You can use indices indicator to show the vertices. Than you should check which vertex you choose to extrude. If you select two separated vertices, they won't automatically connected with face and edge since it is impossible and unusual.

You might accidentally exit the extrude mode with RMB, it will create the vertices in the same place. Causing extra vertices that user might not noticed.