Get a second and third opinion, as well as have the rear t-case bearing checked for play... (you can do this yourself by grabbing the rear yolk/drive-shaft right at the t-case, and seeing if you have any up/down, side to side movement, there should be NONE at all).
you never mentioned how the gear on the sensor looked... any cracked teeth? worn at all? was it replaced with the sensor itself? (usually isn't unless you ask for it to be, and is overlooked most of the time by an average "mechanic") I only ask because if the output shaft has play from a bad bearing or the rear case actually getting out of round/wearing/breaking (known issue with these t-cases) it will cause the teeth on the speed sensor gear to wear or break, and if the gear INSIDE the t-case is plastic (which it is I believe) teeth can be damaged on it as well, causing the exact problem you are having...
I have a '95 that has the unfortunate problem of the rear case damage, and I have gone through 5 or 6 gears on the speed sensor itself as a stop gap measure to keep the truck on the road, but now the gear inside on the output shaft is showing some damage since I haven't replaced the rear case half yet, both need to be replaced SOON for me...
UNDERSTAND, the WHOLE t-case does NOT need to be replaced, Disassembled YES, replaced NO... the gear itself can be replaced, both on the sensor and rear output shaft, and if need be, the rear half of the case itself. Don't get screwed by some "mechanic" looking to make a buck on the notion that you don't know what is going on.
Take it to a few trusted 4x4 or transmission shops, get a few opinions. It could be as simple as the gear on the speed sensor just being old and worn out... a $25, 10 minute fix, tops! (if of course the needed replacement is on hand)
P.S. My opinion on what it *may* be, just by your description of symptoms is that you may indeed have a bad rear bearing, or the rear case problem as well... jumping around under acceleration and then dropping to zero when you let off the gas suggests the rear output shaft is in fact moving, enough that it effects the mesh of the 2 gears, making them skip, which will cause the "bounce" and/or not even mesh at all at some points, resulting in a zero reading....
Let us know what you find out...