I actually liked the treadmill example, but only if we use a treadmill in the way it is meant to be used: to keep whatever is on it stationary. So a few scenarios:
Scenario 1: Treadmill moving at 25km/h, fan in your face blowing at 25 km/h. This is equivalent to the first scenario in the OP. Drag force is Fd. Power delivered by the biker to the bike pedals is 25*Fd.
Scenario 2: Treadmill is moving at 5km/h, fan in your face is blowing at 25 km/h. This is equivalent to the second scenario. Drag force is Fd again, since the wind in your face is the same. Power delivered by the biker to the bike pedals is 5*Fd. The treadmill is moving 1/5 as fast, so the biker is spinning the pedals 1/5 as fast.
Scenario 3: Treadmill is not moving, fan in your face is blowing at 25 km/h. You'll have to put your feet down unless you have good balance. Whether through your feet on the ground or through your feet pushing on the pedals, you have to apply the drag force, which is still Fd. But your feet aren't moving, so you are applying no power to the bike.
Note that in all three scenarios, the relative wind speed seen by the biker is the same and the force of drag is the same, so as far as the wind knows, the power being applied to it (the wind) is the same. But as I have shown, that is not the same as the power applied by the biker to the pedals of the bike. Where does that wind power go? Well that's the trick: the rider is not applying a force directly to the wind, he's simply transferring it from the ground to the wind by applying a force with his legs onto the ground (either through the drivetrain of the bike or directly by standing). But that doesn't really answer the question: where does it go? In all three cases, all of the wind's energy is dissipated as aerodynamic drag and converted to heat, on the cyclist, by the ground.
The power being applied by the person to the drivetrain of the bike is between the ground and the person. The wind provides a force, but the power applied by your legs to the drivetrain is the same if that force is provided by a bungee cord attached to the wall, a person in front of you pushing backwards, or any other static means.