Also, physically speaking (take for example leaving a sanctuary state by Amtrak into another country), do you exit US customs before entering the next country's? Or are they one-and-the-same with no physical "limbo" space?
I'm not sure how it works with Amtrak, and I've never been to Mexico, but I've driven across the US-Canada border in both directions several times, and in general there is a point on US soil beyond which you cannot avoid presenting yourself to Canadian border inspectors. If you pass this point and try to turn around to avoid reaching the Canadian inspection post, you will be stopped by US officers. So, certainly, once you have reached the Canadian inspection post, if they turn you away without taking you into custody then you will need to proceed to the US inspection post.
I am fairly certain that it is safe to assume that if the US and Canada both refuse to admit you then one of them will take you into custody for removal to your country of citizenship or residence.
It doesn't matter what state you leave the US from. The process of reentering the US will be the same. Immigration inspection is entirely a federal matter, as is every aspect of immigration law.
Your other questions:
Has anyone with a valid destination visa/visa-free ever been refused land entry into Canada/Mexico?
I don't know of any specific cases, but of course this has happened. There are some related questions here that may be instances of this; I don't remember precisely. A quick web search shows that such incidents are difficult to find because most of the reports concern Canadian or US citizens, for whom this question is not relevant.
Do you simply get returned to the US? But you no longer have a valid visa/ESTA, nor can you apply for one.
I'm not certain that it's true you can't apply for ESTA. It's possible that the immigration officers would allow you to sit in the waiting room and apply. More likely, though, assuming you were ineligible for readmission or revalidation as described in user102008's answer, they would "parole" you into the United States for a limited period to allow you to depart (parole means that you are allowed to enter the United States without being "admitted" legally) or detain you for removal.