Wouldn't be too hard. Every instance would have a variable for x, a variable for y, and a variable for jump. When you press left or right, change x. If you press up or down, change y. If you press jump button, increase jump and y, next step process jump flag, increase jump and y, next step process jump flag, increase jump and y, next step process jump flag, decrease jump and y, next step process jump flag, decrease jump and y, next step process jump flag, decrease jump and y, clear jump flag if 0. That's all there is to it for an NES brawler. But yeah, you need more than x and y, you're right, but it's just a simple variable you'd process separately. Castlevania 3 was actually already coded to allow this if they had wanted to. The method should have been pretty common in the 90s.
RCR probably "messed up" by using the wrong y-differential allowance. You would think logically you'd just check if two instances have the same y, but this isn't realistic and would make handling very difficult, so you allow for some flexibility by letting the player/enemy attack opponents at different y levels.