by running rich you mean your hydrocarbon count was high, right? that could be from a failed cat converter. otherwise, it'd be odd that his tools show it as rich and the PCM thinks its lean (code 41)...unless the signal isnt making it to the PCM. you can back-probe the O2 and see if its switching like it should be. if it is then you know theres a wiring problem. if it isnt, then it is really running lean.
the EVP (code 84) might be a grounding issue at the PCM. since you have 12v at the solenoid, i assume the PCM grounds it to open the valve. if the ground the PCM uses for this isnt solid, it will cause an open circuit. im sure the codes 33 and 34 will go away once you get the EVP to open when commanded to by the PCM.
the VSS should be located on the rear differential. on the top, slightly towards the front and drivers side of the vehicle. if its missing, someone swapped a much older axle into the truck and the harness is probably tucked up out of the way somewhere.
i dont know what to say about the code 89 other than you probably wont be able to fix it without swapping computers or swapping in an automatic. MAKG, if your still watching, do you happen to know what kind of feedback the PCM looks for here? is there any way he can trick it to get the CEL off?
you might try making a seperate post and see what others that have done 5 speed swaps have done to clear this code.