Is it reasonable just to cite another paper's results at face value?
In my opinion, there are only few limited cases where this would be acceptable. For example, when comparing industrial-scale systems, or comparison of qualitative features of the works. Also in the case there exist an established set of benchmarks and your algorithm can solve some of those the other can't, you do not really need to reimplement. Possibly also when testing the algorithm cannot be done in a reproducible manner (industrial-scale field tests). When it comes to experimental efficiency, however, I think you usually do not have much choice and should reproduce the others results - if possible at all.
What suggestions would you give to this conundrum?
Depends on what you need the cited work for. In the case you developed an algorithm which is supposed to be more efficient than the cited one, to prove your point you need a controlled experiment when both methods are run under same conditions (e.g., implemented in the same programming language, and run on the same system etc.) and with the same set of benchmarks. In such a case, if you want to demonstrate your point properly, your best is to reimplement (or ask the authors for their implementation and adapt it to your conditions) and run head-to-head. Otherwise your performance curves are going to be incomparable. For good examples of how to do this, see for example comparisons/evaluations of experimental performance of planning algorithms, or SAT solvers.