Correction: We had rockets that could land on the moon. There was no orbital-class rocket that could launch from Earth and land back at launch site (or further downrange). The difference in gravity + lack of atmosphere is a big factor.
It is like saying that the Apollo ascent module could get to orbit and therefore we can clearly make practical SSTO vehicles.
> We had rockets that were reused with the shuttle.
If you consider throwing away the massive external tank and external SRBs (without which it couldn't fly) and completely re-building the three engines after every flight.
If we didn't have to worry about fuel, we could. "put in enough fuel so it can land" is not a hard problem to solve with earth rockets, it just costs payload.
> completely re-building the three engines after every flight
It's complicated but the level of rebuilding was driven more by very high standards than it actually being necessary to make it launchable.
I am pretty sure that the convex optimization algorithms used by SpaceX's landing systems are a very recent invention (http://larsblackmore.com/publications.htm). As for worrying about fuel, what's the point of a rocket if it cannot take any payload?
Who said it was impossible to combine them? And "impractically expensive and counterproductive" doesn't count.