Z-Axis zero/home position is higher than the actual print starting position
Check the Z-drive for any component looseness. Look at belts, gears, anything with screws. Wiggle things mercilessly checking for play. 

At the start of a normal print run, the the print head typically rises up very high as the head warms up (depends on software) and then lowers to print. If your homing paper test happened with the head near the limit switch, then the difference between those two use cases is the Z-distance traveled to get to the same place. You have eliminated software and electrical considerations, which leaves mechanical considerations. A slipping gear or belt might contribute to this odd behavior you describe.