Am i missing something, is the need to land vertically a requirement of a fragile fuselage? Seems wasteful to carry extra anything (in this case rocket propellant) to space, just to avoid having to re-right the rocket when you get it back on earth for a subsequent launch. Is extra fuel payload < landing gear or parachutes?
You also can't land on a ship with parachutes. You don't have enough control. You can still land at sea, but then you have to actually land in the water, which means getting seawater on all your rocket hardware. That causes lots of problems when you want to use that hardware again.
SpaceX did experiment with this approach. Here's a picture of the second Falcon 9's interstage with parachutes packed inside:
http://i.imgur.com/PGXIqKX.jpg
But it turned out not to work so well.
NASA had some success with this approach on the Shuttle SRBs. It's easier with solid fuel rockets, because they're less efficient and built tougher. Even then, the cost of recovery and refurbishment ended up roughly breaking even compared to just building new ones each time.
As far as "wasteful" goes, that depends on what you're looking at. Saving fuel for the landing subtracts from payload capacity, which is wasteful in theory... but in practice, many payloads are smaller than the maximum anyway. If you suffer a 30% payload penalty, but you're launching a satellite which is 40% smaller than your maximum, then who cares? The only waste is some extra fuel, which is super cheap. The full fuel load for a Falcon 9 launch is something like $200,000, compare to the total mission price of around $60 million.