Thankfully, you are wrong about that! Just like you don't need a cooler source _from which to source cold_ in the summer with AC. Technology Connections has a fun (well, to me) video on how heat pumps work and are great. Literally just AC units running in reverse, thanks to having a valve.
At a certain temperature differential you need to source "heat" from elsewhere, which is why up north you either need a geothermal heat pump (underground piping) or you supplement with gas or electric heat.
Some very efficient pumps can work down to 0 degrees, but most start losing efficiency at 25 to 40 (Fahrenheit).
For some parts of the world, a heat pump is perfect - pump in heat in the winter and heat out in the summer, but when the outside temperature can hit -40º Fahrenheit (which is -40º Celsius), you're gonna need something else.
For the overwhelming majority of the world they are perfect. Even in high latitudes, they might only reach those extremes for a few days in a year, that's when you would require a backup.
Losing efficiency is fine since they are so ridiculously efficient to begin with.
100% efficiency is rather low for heating. Heat pumps easily give you 400%. Efficiency in this case calculated as: generated energy (in heat) / electrical energy. Efficiency goes beyond 100% because heat is extracted from air or water.
Still, not a bad idea to run Folding@Home all winter.