I've used a voltmeter on the wiring to determine its not at the plug. Also replaced the original outlet.
This might be "phantom voltage" - i.e., voltage read when the circuit is effectively dead. Or it could be something else.
Troubleshooting process is to start at the beginning - the breaker - and work your way out.
You could have a bad breaker, but normally breakers will either fail off (in which case there is no real danger, but the circuit will be dead, but you may read phantom voltage) or fail on (extremely dangerous). But a failed breaker would be extremely unlikely to cause a "real" partial voltage - electricity doesn't work that way.
Then work your way out to each receptacle or other device (switch, lighting fixture, etc.) in the circuit. Any place that there is a junction - a wire nut, two wires (or a looped wire) under a screw, wires on two sides of a receptacle - could have the possibility of a loose or broken connection. A broken connection will result in the rest of the circuit being dead (but again, possibly phantom voltage). A loose connection can result in high resistance (among other problems), which could cause all kinds of strange readings.
Pay special attention to "back stab" connections. This is where a wire is stuck into the back of a receptacle instead of around a screw. Back stabs are more prone to failure than screw connections. If you find any, move them to screws instead.