Go back to this mechanic or find another to rescan for codes. If the VSS replacement did not correct the code related to VSS, there may be a wiring or ECM problem. BTW, how is the speedometer working? When the Engine Control Module senses a loss of the VSS signel, it cannot make a decision on when to commmand the shift of the transmission so it will drop into limp home mode which is usually second gear and torque converter unlocked so your tach will surge.
The Toyota transmission is a pretty robust unit. Unless you had or have burnt dark fluid, I would not think a rebuild is in your future. More than likely, this is a control problem that will not cost a lot to fix.
Hope that helps