First of all, there is no such thing as a stall speed, but that is a topic of its own.
The ATC system has numerous ways of dealing with keeping aircraft separated, even at high levels. Let me try to summarize some of the most important ones, starting with the planning that happens when planes are still at the ground at their departure airport, working our way towards what happens when they do get (too) close.
Aircraft flying en-route will follow pre-defined routes (known as airways or RNAV-routes). Airways are like highways in the sky, and ensure that air traffic will fly in predictable patterns. This makes it a relatively simple task of predicting potential conflicts (a conflict in this denotes a situation where two or more aircraft get closer than the prescribed separation minima), because every flight will send a flight plan in advance, detailing the planner route, level and speed to fly.
In addition to just specifying lateral paths, airways also have vertical restrictions. This means that, when following a certain airways, you have to be flying in a certain range of vertical levels. It is quite typical for airways to limit traffic to fly at either “even” or “odd” levels. An even level in this case could be 34,000 feet, 36,000 feet, 38,000 feet and so on, while an odd level could be 33,000 feet, 35,000 feet etc. The general rule in most parts of the world is that airways going east will force traffic to fly odd levels, while airways going west will force traffic to fly even levels. This acts as a fall back procedures, which in principle means that two aircraft flying in opposite directions (one heading west, the other east) will never fly at the same level. Of course, it is easy to realise that this rule cannot cover every potential conflict.
We have now looked at some of the permanent infrastructure in the sky, but let’s zoom in further and look at the tactical aspect of flight planning, specifically, air traffic control.
Air traffic controllers, whose job is it to “maintain a safe and expeditious flow of air traffic”, use various means of technology to keep aircraft in the sky separated. In many parts of the world, their job is achieved by processing large amounts of information received in real time about air traffic using radar technology, and communicating with planes using radio. In places where no radar coverage exists, such as over large oceans, only radio is used. If no radar is available, pilots have to periodically call up on the radio and make a detailed position report, stating the location, level, speed and planned route of the aircraft.
Using either radar or pilot position reports, air traffic controllers will predict potential conflicts and try to solve them. (This is really where the essence of your question will be answered).
There are a few different separation minima. For the sake of simplifying the answer slightly, let’s assume we are working with only three:
vertical separation (the vertical space required between two aircraft who pass each other at (almost) the same position
horizontal separation (the horizontal distance required between two aircraft passing each other at the same, or near the same level)
time based separation (the minimum time required between aircraft following the same route, at the same level)
The vertical separation minima is generally 2,000 feet, however, as aircraft altimeters and radars have gotten more accurate, this has been reduced to 1,000 feet in many areas of the world (called RVSM airspace). Considering the fact that most commercial aircraft cruise in a level band between 30,000 feet and 40,000 feet, this gives you 10 different levels to work with (30,000, 31,000, 32,000 and so on). That actually means, that using vertical separation alone, it is possible to have 10 different aircraft at the same position, at the same time, while they are still separated.
Of course, forcing an aircraft to fly at a non-optimum level is not the perfect solution in terms of fuel efficiency, but it can often be the lesser evil (as opposed to forcing speed changes etc.)
Horizontal separation is achieved by (temporarily) changing aircraft routes. This might sound like a big deal, but in fact, potential conflicts are usually detected early enough that only very small adjustments are required. For two aircraft on intersecting tracks, if you detect the conflict between them 10-15 minutes in advance, it will often be enough to instruct either of the aircraft to adjust their heading by as little as 5 degrees to prevent the conflict. Once they are passed, you simply instruct them to return to their planned routes. This will only result in marginally longer flight paths, and so will only cause a small impact on fuel consumption.
Time based separation using speed control is probably the last resort in most cases. Instructing an aircraft to change it speed for a long period can have a serious impact on fuel efficiency. However, there is no need to worry about aircraft being forced to slow down enough to risk a stall (or speed up enough to risk damage to the aircraft). For starters, the pilot would never accept such instructions from air traffic control, and ATC would have to come up with another plan. In addition, air traffic controllers have been trained thoroughly, and are well aware of the performance limitations of different aircraft.
As with heading adjustments however, it might surprise you how little it takes to ensure separation using speed control. This is because most modern airliners actually fly at very similar speeds (usually between 75% and 85% the speed of sound). Changing the speed of an aircraft by just 1% will have a huge impact over a long distance, such as a flight across the North Atlantic Ocean. And so, as with levels, where in principle you have around 10 usable levels, considering 1,000 feet minimum vertical separation, you might also have about 10 different speeds to work with.
Overall, speed control is a very efficient way of maintaining separation that already exists (e.g. two aircraft following each other on the same route, at the same level), because instructing them to fly at the same speed will ensure that the latter aircraft never catches up with the former. Horizontal and vertical separation can be applied when separation needs to be established, for example between aircraft on intersecting or opposite routes.
Finally, let’s briefly discuss what happens if the system fails. That is, if air traffic control, for one reason or the other, fails to provide the required separation between two aircraft.
All modern commercial aircraft are equipped with airborne collision avoidance systems (ACAS), the most common form being the TCAS. TCAS equipment of two different aircraft in proximity to each other communicate directly to determine a) if there is going to be a conflict and b) how to best solve it. I won’t go into details here, but basically, if two aircraft are predicted to get too close, the TCAS systems will work out how to solve the conflict, typically by instructing one aircrew to descend while instructing the other one to climb. The fact that the TCAS systems communicate ensures that the same instruction is not issues to both different aircrews (imagine the airplanes flying toward each other at the same level, both being instructed to climb …). If the TCAS goes off, all instructions received from the TCAS system takes precedence over air traffic control instructions (much like air traffic control instructions take precedence over the general airways rules we covered earlier).
So to sum it all up – aircraft separation comes down to planning. If it is predicted, based on flight plans received from hundreds of different aircraft, that a certain route or level will be very busy for a certain period of time, then the system will simply not allow more aircraft to fly this way. They will be re-routed or their planned level changed, even before they leave the gate (allowing them to bring extra fuel, if required, to fly a slightly longer route or at a non-optimum level). Once in the air, air traffic control will make use of vertical, horizontal and time based separation, and, if all else fails, on-board computer systems will ensure that no collisions actually occur.
Edit:
A few references for further reading:
Mid-Air Collision - On the consequences of losses of separation, and how to prevent them
Conflict Detection - On detecting potential conflicts in the ATC system
ATM Sector Management - On predicting capacity and responding to demand in the ATC infrastructure
Flight Plan Filling - On ATC flight plans and their content
Guidelines for providing Radar Separation - A few example calculations
Airborne Collision Avoidance System (ACAS) - On ACAS, the last resort, when all else fails
Reduced Vertical Separation Minima (RVSM) - On the parts of airspace where the minimum vertical separation is reduced from 2,000 feet to 1,000 feet
