Every single main faction on TBC and WotLK is designed so that you can reach Honored by just quests. Just saying. There isn't a SINGLE time when I've played on a 1x realm that I didn't get all factions to Honored before hitting max level. Of course, you need to do selective questing for this to happen, like completely ignoring BEM and Nagrand, but after 12 years of WoW I've gotten used to this.
Lowering the requirement on Medivh earlier than intended would, thus, be disastrous. It would basically allow players to start doing HCs as soon as they hit 70. Now imagine a blue/green geared 70 that has never done SH, SHH, Steamvaults, SL, BM or all the Tempest Keep dungeons (since those dungeons are 68-70lvl and chances are little that they have done these before 70) joins your HC group. Yeah, nobody wants that.
I could vouch for either a rep increase or a key nerf for Outland. But I really really don't think it's a good idea for Medivh, unless they do it to draw players there (which is not a bad reason, actually).