Hey Mr. Greg,
According to my interchange info the transmission shows to go from 98 to 04 as long as it has the 4 cylinder regardless of the model number.
Also about the RE4R01A unit, my interchange system shows that it was only avalible on Frontiers in 99 - 00 and it had only came in the 6 cylinder models... The other problem is that it's 4WD which means its obviously going to have a longer output shaft and the tailshaft housing will be different. I'm not sure what other differences it may have. So yes your correct the RE was introduced in 99 but only in 6cylinder 4x4 models. (all 6 cylinder models in 1999 were 4x4). In order to have the RE trans in 2000 the Frontier has to be a 6 cylinder, 4WD, be produced up to 08/99, and it has to be a king cab.
I know that for my Chevy a 2wd trans can be used but all you have to do is swap over the output shaft, the tail shaft housing, and cross member.
I actually just brought in a 03/98 frontier with the RL transmission if you need a good one.