The king shouldn't have to individually review the petitions of adventurers. Seems a bit beneath his station, really. Isn't one of the reasons he has lords and knights is so they deal with the dirty masses and he only has to deal with the gilded gentle-born?
I too found it rather difficult and time consuming to make it to the nobility. Just barely not prohibitively so.