Yes it is impossible without energy storage to move the vehicle from left to right.
I see two situations here:
1. There is no energy storage and you are wrong.
2. There is energy storage but it doesn't matter because the vehicle moves from left to right as long as the paper is moving.
That's the crucial thing, is it? That the movement is not a temporary 'until the energy is gone' thing. Even if the alleged energy store was storing and releasing, storing and releasing, the thing is moving left to right without at any point moving right to left. And it will keep doing that for as long as the paper holds out. So how it does that in movement terms, in what way the energy is tranferred, is just a sideshow and irrelevant.
You entire supposition of the energy store is that it cannot last indefinitely, so the Blackbird can only slow down to below wind speed once it has used the store to get above wind speed. But here your store (that is, your energy store, wherever you happen to think it is) is able to keep supplying the left-to-right motion forever.
1. Sorry but how can you say there is no energy storage when is so clear seen in video and is clear to see the stretching of the rubber belt.
2. Look more closely at the video and read about stick-slip hysteresis if you did not heard about that before. The combination of those two the energy storage and stick slip hysteresis is what makes the vehicle move forward you just need to understand what you see in the video.
Vehicle is powered by the paper (hope you agree with that) so it can move forever but speed of the paper will always be higher than average speed of the vehicle. Vehicle speed can exceed temporarily the speed of the paper due to energy storage but the average speed is much lower.
What you see represented there is a the equivalent of the blackbird version that uses the propeller as a wind turbine and drives against the wind direction.
Please explain how vehicle is able to move from left to right.
Here is my explanation
Front wheel starts to spin while back wheel is locked and this is only possible if there is energy storage.
The belt acts with exactly the same force against the large pulley on the back wheel as it is against the small pulley on the front wheel.
Since the front wheel pulley is smaller the front wheel is the one that rotates but not slipping up to this point.
When enough energy is stored in to the belt the force that belt acts against the wheels will make the front wheel slip.
There is a minimum force threshold needed for the wheel to start slipping but once that happens the force needed to keep the wheel slipping (you may have experienced this if you ever drove a car on ice or snow).
Because of this since the back wheel is not slipping it can push the vehicle forward using the energy stored in the rubber belt and when the rubber belt energy drops low enough that it can no longer push the vehicle the front wheel stops slipping and things as seen in the video repeat.
If you do not agree with my explanation of what happen to the vehicle in my slow motion video please provide your explanation in a similar way.