Gaining no EXP I'd be fine with I think.
Strikes a nice balance between letting you use the powerful buddy you earned and letting him carry you through too much of the game too easily. Not sure I can go for the insubordinate thing though: if I were playing, that would probably mark them as "unusable" for me, even if the chance was very, very low: Demon can be too darn deadly to put up with that extra risk just for a higher level ally!
Negotiation recruitment already scales with level, as do (by definition) any recruitments based on protecting or killing the would-be-ally. Haven't really done this for other types though, and probably should figure out a way to do so. Trick is keeping them possible while making them harder: though the types that don't currently scale well (kill other demons, chase me)) are usually the easier ones anyway so there should be room for that.
Edit: As an aside though, this particular topic's status is pretty near dead. I don't want to close it since I may need the mechanic again one day, but at the moment this is somewhat less concerning than it was before. Game difficulty has increased a bit in general since the original post, making the high level buddies a bit more of a "oh thank Blankie, some help!" and less of a "win mode activated."