One of the things that seems to happen as one ages is that maximal oxygen uptake decreases, though I suspect that, as a trainable factor, the reason for this is that masters runners aren't doing the correct workouts. Top elderly athletes like Ed Whitlock have had unusually high VO2max recordings; Whitlock also had an unusually high maximal heart rate for his age - whether he had an unusually high rate when he was young or his maximum decreased unusually slowly (probably both) is unknown. His training appears to have consisted of "slow" 2-3 hour runs and frequent races, without what most would consider typical VO2max training.
But let's take a look at the matter.
VO2max is measured by running on an inclined treadmill for about 12 minutes. It's a good measure of one's ability to run 12 minutes, so it's best for 5K comparisons. Jack Daniels, considered the foremost authority on the subject, says training for it is done at (or very near) maximal heart rate, ideally in 5 minute bursts. I can only manage my maximal heart rate under unusual circumstances and for at most 2 seconds, as other factors impede me before I get there. I think that this may be common; if something keeps a master runner from being able to run at a pace that would correspond to their actual maximal VO2max, they will have a lower measured VO2max, because that's all that can be measured. I'm going to say that VO2max training is done at the average heart rate one can manage for a 5K, which may be considerably lower than one's maximum heart rate. That leads to some possible explanation of how masters runners should train in order to increase their VO2max.
This is probably the most straightforward method. If you can mimic the effort without the pounding effects on the body, you should be able to do a lot of VO2max training, so you could train at the (assumed) VO2max heart rate while doing some other activity; cross-country skiing is probably best (the highest VO2max recordings have been measured in cross-country skiers), cycling probably the most convenient.
When you run long, either you slow or your heart rate increases over time (cardiac drift), or both. If you run long enough at a pace above an ultramarathon pace, your heart rate should eventually hit your VO2max range. Unfortunately, running this long seems to lead to overuse injuries and running a fast-ish pace for a long time is close enough to racing that it requires a very long recovery, cutting down the amount of useful training you can do. A way around that is to do a progression run, where you intentionally run the last few miles faster (necessarily running less distance); cardiac drift means that you start the harder section with an already increased heart rate, so it doesn't take much extra effort to push to VO2max. I personally find this next to impossible to do, but there is another option. If you have a long hill at the end of a long run, one's heart rate has to climb as one climbs the hill (often even when slowing down), allowing VO2max training at a relatively slow pace.
Intervals vs Hills
There are two different ways to use interval training to improve VO2max. One is to use short intense repeats with very short recoveries, e.g. the Billat protocol of running for 30 seconds at the pace one could manage for 6 minutes, followed by 30 seconds at half that pace, repeated as long as possible (24 repeats seems to have been the most done in the study). Because one's heart rate doesn't fall enough during the recovery, one's heart rate during the hard parts climbs quickly and one even eventually hits the VO2max heart rate during the recoveries. This is problematic for older runners such as myself, because the very fast pace, particularly on curves, leads to injury.
The other method is the standard. 3 to 7 repeats of 800 to 2000 meters at 3K to 5K pace (about 4-6 minutes) are done, with approximately half as long a recovery as the time spent running hard. As Daniels points out, the first two minutes of each repeat may be spent in reaching the appropriate heart rate, so one doesn't run the entire workout at VO2max. As one ages, it may become difficult to run much more than two minutes at this pace, so the workout falls apart.
The alternative is to switch the workout to a hill of 4-6% incline. This causes one's heart rate to climb much faster, so you can run slower and get the same results, plus there's less of a lag time building up to the desired heart rate. The challenges here are that running downhill is stressful and can lead to injury and taking too long going down the hill could let one's heart rate drop too much. This could be obviated by doing the workout on an inclined treadmill.
It's quite possible that Whitlock was running at his VO2max during his races and that this was enough to keep him in shape. To duplicate this, one would have to race frequently and be careful to both not over-race and to not run so hard during the races that a long recovery is needed. Very competitive-minded runners such as myself find running races as low-key time trials rather than all-out races a challenge. It's probably easier when, like Whitlock, you could jog almost any race and win an age class award.