I used to stick rigidly to the H/V rule, even if it meant two vias and a .2" trace because that tiny gap was enough to sneak a trace through and get you out of trouble. Towards the end of the layout when you where 95% sure you wouldn't need to run (m)any more traces in a given area you could get more creative and not be so pedantic about it.
Once the board was totally laid out I would spend another day or so removing as many silly layer changes and vias as possible. But as you say it was difficult to make mods with tape so you were less included to do so. It was also a good way to add bugs if you ripped up a few pieces of tape then went to lunch 
At least now we get a flying wire as soon as we delete a trace, not to mention the DRC.
Rob