The most obvious thing would be friction on the cable, but it sounds like you have checked that. Make sure the cable slides smoothly without resistance through the entire path including the metal 1/4 circle piece where it goes into the brakes. Check for kinks in the housing. And, just in case, make sure something isn't getting pinched when you flip the bike over - I've seen that before.
If the cable's good, it is probably the v brake itself at the wheel not having enough spring back. With the cable detached, both sides should pull away from the rim fairly strongly. It is the springs on each side of the brake arms that pull the cable back through when you release the lever. It's tough to tell from the video, but when you adjusted the springs on the v brakes, you may have put them to the weakest position instead of the strongest. It can be confusing which is which. You also might take the whole brake arm off the frame by unscrewing the bolt where it pivots. The post it rotates on may have rusted. Clean up the post and inside the arm of the brake, grease, and reinstall.
good luck
It appears the brakes themselves have a strong enough spring at the wheel. It sounds like maybe you are not running the cable through the 1/4 circle metal part (noodle)when you test the cable. If so, maybe the cable is rubbing there. It could be it is rusted inside. It could also be a metal burr or that the cable goes into it at a weird angle. Just cleaning it may not fix the problem. Make sure the ends of the housing are clean and not kinked. Make sure the housing fits into the noodle fully and at a smooth angle so there's no sharp bends. Test the cable running all the way through the path it would follow, but just not tightened down in the brakes. If it isn't the cable or brakes themselves, I'm not sure what else would cause that.