Natural enemies boost deep evolutionary fitness?
The question is interesting.

I am afraid about the use of the word "fitness" in you question. The fitness is usually defined as the number of offsprings an individual can sire in its lifetime. Most often we talk about relative fitness which is the relative number of offspring in an individual can sire in its lifetime compare to the individual in the population that sire the greatest number of offsprings.

How would you compare fitness of individuals between different species? Just by counting the number of offspring they left behind? Or did you mean that most fit species are actually those species that can outcompete others? If yes, then I would say that saying


  Two species that reduce one another's fitness on microevolutionary (short-term) timescales can increase each other's macroevolutionary (long-term) fitness


can be restated 


  Two species that reduce one another's fitness on microevolutionary (short-term) timescales can increase each other's macroevolutionary (long-term) species competition ability


and it is actually just a special case of


  One species that evolve under many strong selection pressure ends up being a very competing species.


The explanation is the following:

One species that undergoes one selective pressure, will see its genetic variance decreases. The weak individuals will disappear letting places to the strong individuals. Then newly arisen variance (mutation) will come up only in the strong individuals (as the other ones disapeared). This is what J.Gould meant by saying "Natural selection creates the fit". As a consequence a species that undergo many successive selection pressure will end up with purified and very strong genotypes while, in a species that were free to evolve without selection they would have evolved many different genomes with some good mutations nested in very poor genetic background.

You could as well use the concept of lineage selection and states that lineage that succeeds to outcompete others will thrive while species that suffer from competition with other species will get extinct. As a result, if you compare all species that were in competition with another species in the past with all species that were not in competition, you will find out that those that were in competition are more resistant to competition. But I guess this is not exactly what you meant when saying: "Two species that reduce one another's fitness on microevolutionary (short-term) timescales can increase each other's macroevolutionary (long-term) fitness"

Finally you might think of the ability of species to evolve better. This ability is called "evolvability" (see this book for example). You might say that species that undergo many selection pressures were selected to resist to newly arisen selection pressure. As a result, species that are under competition might end up with a greater evolvability than those that were not under selection. Resulting that species that were under competition will tend to increase to always increase their fitness in the long term.