What is known about the phase of matter at very high temperature and enough pressure? Are there theoretical reasons for or against the existence of materials that will not become solid at some fixed, sufficiently large temperature when enough pressure is applied? Or is this even the normal state of affairs?

The usual phase diagrams typically only give a finite portion of the thermodynamical state space, probably as more cannot be experimentally tested.

But theory might tell us what happens, one way or another.
There is a point in which it is too hot for a molecule to remain bonded and will break apart, no matter how much pressure is applied. Now with more pressure the electrons and nuclei will start free flowing in what is known as a plasma. And add a little more heat and fission happens.

So basically the reason they don't show you any more of the curve because your molecule under enough pressure and heat is no longer a molecule.