I think you are onto it: Why don't we use a heavier hydrogen-bearing molecule that is actually possible to store as energy bearer?

You mention natural gas; that's one option (CH3 = methane).

Ammonia – NH3 – is another that's starting to look promising and really could use some of hydrogen's hype: https://en.wikipedia.org/wiki/Ammonia#Fuel

Not for personal transportation, though – it's toxic – but for big engines in ships and airplanes.