There are lots of questions here that I will try to answer, hopefully I'll get to them all...
It's hard to "just fly higher" when you consider passenger planes. Supersonic military aircraft like the SR-71 do fly ridiculously high. It's service ceiling is 85,000 feet! But, it has the advantage that it doesn't need to keep anybody but the pilot comfortable. The issue deals with pressurization. As you increase altitude, the aircraft must also be able to withstand a larger pressure differential if the cabin will be kept at a comfortable pressure. Most very high altitude military aircraft do not pressurize the cabin; rather, the pilot wears a pressure suit. Imagine if you had to suit up for a flight to visit relatives!
It's not that we can't build a plane that can withstand the pressure difference, but doing so would require very heavy or very expensive materials. The former makes it much harder to fly while the latter makes it not very commercially viable.
There's a reason going past the speed of sound was called "breaking the sound barrier." There is a magic number called the Drag Divergence Mach Number (Mach number is the fraction of the speed of sound at which you are traveling). Beyond this number, the drag increases tremendously until you are supersonic, at which point it decreases quite rapidly (but is still higher than subsonic).
Therein lies one of the biggest problems. You need very powerful engines to break the barrier, but then they don't need to be very powerful on the other side of it. So it's inefficient from a weight/cost standpoint because the engines are so over-engineered at cruise conditions (note: this does not imply the engines are inefficient on their own).
There's no denying that it will get hot. It is storied that the SR-71 would get so hot and the metal would expand so much, that when it was fully fueled on the runway, the fuel would leak out of the gaps in the skin. The plane would have to take off, fly supersonic to heat the skin enough to close the gaps in the metal, then be refueled mid-air again because it used it all up. Then it would go about it's mission.
At the Mach numbers for a commercial aircraft, the heating would not be as extreme. But it would require some careful engineering, which makes it more expensive.
So why can't it just fly higher?
Ignoring international law for a moment, there's several reasons why flying higher just isn't as viable:
- Cabin pressure issues
- Emergency procedures: Let's assume for a moment we could pressurize the cabin. In the event it loses pressure, what do we do? The normal procedure would be to dive down to a safe altitude, that takes considerably longer from 60,000 feet than 30,000 feet.
- Drag is proportional to density, but so is lift. This means to fly higher, an aircraft needs bigger wings. But bigger wings mean more drag, so it gets into a vicious cycle. There is a sweet-spot that can be optimized for an ideal balance, but that means that "just go higher" may not be a good option.
Ceilings and Speeds
This one doesn't have to do entirely with legal issues, but that's part of it. A service ceiling is defined as the maximum altitude at which the aircraft can operate and maintain a specified rate of climb. This is entirely imposed by the aircraft design (laws may require a minimum ceiling, but not a maximum... although they may restrict a plane from flying at the maximum).
Likewise, an absolute ceiling is the altitude at which the aircraft can maintain level flight at maximum thrust. Naturally, as the plane burns fuel and becomes lighter, it needs less lift to stay at the same altitude. But the lift force is based solely on the geometry and speed, so actual lift will exceed what is needed and the plane will climb. As it climbs, the air density drops and so does lift. This means as the plane flies, it's absolute ceiling actually increases.
Now for the speeds... Commercial aircraft fly as close as they can to the Drag Divergence Mach Number because it's the most economic point to fly. The plane goes as fast as it can go without the drag coefficient increasing tremendously. This is usually around Mach 0.8. But they can, and often do, go faster than that.
It's not unusual for an airplane that is delayed taking off to land on time or even early. This happens because they can still go faster than they normally operate (not significantly of course, perhaps Mach 0.83-0.85). It may cost some more fuel because the drag coefficient is likely increasing as it approaches Mach 1, but a delayed plane is more expensive for the airline than the extra fuel used (maybe not in direct dollars, but in PR, reputation, etc.)