I don't really see this as a running problem. RPing that commoners are beneath nobles doesn't mean you have to beat up every one you see. I've had advs arrested without cause and even executed. It's common for people to value the services of a particular group even if they look down on them as inferior. Just look at the untouchables of India. They're the lowest caste, but some actually make a good living because they're the only people who can handle dead cows which creates a source of leather and provides a service cleaning them from the streets.
I think it's more interesting for role play if nobles must begrudgingly accept the services of filthy adventurers.