The type of creature that flies well is radically different from one that swims well or can burrow into the ground. From an evolutionary standpoint, there is rarely anything to be gained by changing a design of a creature that survives well in one type of environment. In order for a predator to exist that navigates all three media equally well, there would have to be a good reason.
You mentioned the lack of food, however the lack of food means there are few animals in any one environment to sustain a predator. You don't typically see creatures evolve to surpass problems like this because the changes are too radical. It is a bit like asking why gazelles in Africa didn't evolve wheels or wings to escape the cheetahs. Such changes don't happen overnight, and they certainly don't get it right on the first try. Progress in evolution tends to be favorable to conditions that encourage a particular trait. Any mutation in a gazelle that doesn't immediately improve speed is going to get eaten by the cheetah before it has a chance to pass on its genes to its offspring, all the moreso if a gazelle, in the process of evolving "wheels" becomes triple jointed.
Generally creatures that can fly have very few natural predators, since they are the most ellusive of all creatures to catch. Even then, most of these predators are creatures that attack nests, and not while flying because it is very difficult to catch your prey that way. The only way something like this would be possible is if there were predators that easily caught prey in the air. Just like you see flying fish leaping out of the air to temporaneously escape a predator in the water, you might begin to see birds that can dive into the water to escape a flying predator. Once you have creatures that can do this, you might then see an evolution of the predators themselves that could dive with the birds in order to catch them.
However, it wouldn't make sense to have a predator exist without sufficient prey, and this type of prey would only exist with this type of predator (oddly enough, in the food chain, one wouldn't exist without the other). And if this predator does so despite having many food sources, you can see that such a creature couldn't exist.
Evolution encourages traits which cause that creature to perform better without losing any edge, and this type of predator would require too much of a change that it would deteriorate too much its ability to catch prey in other environments to merit the change in the first place.
However, you tend to see many strange creatures in environments where there are many creatures, not few. Perhaps such a predator could exist, but not because there is lack of food but because it itself is prey and must escape predators better specialized in hunting only in the air, or only in water.