It very much sounds mechanical so this is the first place to start.
I would move Y-axis to one side and remove stepper and also remove bolts connecting ballnut to Y axis. Then slide Y axis across gantry to feel if binding on rails.
Then rotate ball nut and ballscrew by hand to see if tight or sticking. Also, check for any axial movement of the ball screw in bearings. Should be none.

If both move freely with no floating in bearings etc then it's most likely an alignment issue with the ball screw.

Also just for reference don't mess around any more with Velocity. Just set it at say 1500 with 500 Acceleration and it should be fine for now. Can always find it's limit when know mechanical is ok.

Also check that you have the Jog percentage set to 100% because some of those movements looked slow.