Voltage regulator from first principles - why is power dumped in the transistor?
I put this together from first principles without referring to any kind of reference on how voltage regulators are usually designed.


Not a good start, but you've actually ended up with almost the exact design of most linear regulators. But the "first principle" you've forgotten about is the MOSFET linear region. Have you tried this thing in a simulator? The system will settle at a point where the transistor is half-on, dissipating power as a resistor.


  When V1 is less than about 7.5V, the output voltage never hits the 5V threshold, but instead hovers around 4V. I have tried this with varying loads but it simply does not function below that input voltage. What is the cause of this?


This is called the "dropout voltage". It's due to limitations in how close to the input rails the opamp is capable of driving; you lose approximately 0.7V in the output transistor of the opamp and another 0.7V because of the threshold voltage of the MOSFET.

You might be able to do better with a better op-amp than the ancient, obsolete 741. Otherwise, you're trying to design what's called an LDO: low-dropout regulator.