I should start by clarifying that when I say "Isometric" I am talking more broadly about top-down games that use a "cheat" to display things on a z-axis, rather than being limited to games in this style with a locked 3/4 angle like Sonic 3D Blast, Q**Bert* or Fallout (thus, I've not used the "isometric" tag on this question). This being the case, my target includes most 2D JRPGs and the 2D Zelda titles but does not address games that are truly top-down like Smash TVGrand Theft Auto and Robotron 2084, nor those with true 3D like--well, most games nowadays.
But enough housekeeping. I have made an isometric JRPG system for a college project (using pygame, for full context), and have had issues with rendering order from day one. IIRC most isometric games just sort gameobjects by their y-value, but this seems to stop working when objects can stand on top of eachother. Since all my terrain is objects...there are problems.
I found a cheat that allowed me to depth-sort cubes by factoring in the z-position, but the cracks in thethis system show ever more clearly as the project progresses. Angled boxes show some glitches that could probably be overcome, but conical terrain seems to break it entirely. The system can be limped along for the purposes of the project, but thinking about the future (and a proper re-build of the system) leaves me unsure of what to do so that depth sorting works properly.
My first thought was to do depth mapping akin to 3D rendering. In theory would work thus: before a shape is rendered, try drawing the depths of each pixel to a depth map. Only pixels closer to the camera than the pixel they are trying to overwrite will be drawn. Any pixels that couldn't be drawn on the depth map shouldn't be drawn on the screen.
This should solve my problems, but it also sound a bit expensive. Surely suitable for modern hardware, but not something any of the old isometric games would have done--at least, not in real time. So my question is this: did old games have a more efficient method for isometric rendering, or did they just pre-compute depth values?
Also, just to clarify: yes, many old games surely solved this problem by cheating (i.e. place a trigger under the bridge that renders it above the player when colliding) or avoidance (i.e. no bridges at all). It's a valid approach, but I'd rather not.
EDIT: As per DMGregory's suggestion, here are some visual aides.
Here are the sorts of things I'm shooting for:


This is a traditional "Isometric" game--not explicitly what I want, but not counter to it either:

