This is an electronic speedo, right? I think you were on the right track with the VSS replacement, but did you turn it right on install? If it's like the cable speedo's, you have to turn the VSS in the bore in the tcase output so that the little arrow points at the number of teeth on the VSS gear on the housing. It's not likely the speedo drive gear is toast, because it's steel grooves cut in the output shaft. Check the teeth on your new and old VSS driven gears. You may have been unlucky and got them almost in mesh.

Another cause is the outputshaft housing bushing walking forward until it interferes with/eats up the VSS driven gear. Had any Ujoint problems?