Certain servants would almost invariably travel with their employers, so they could be moving about a lot, if not precisely of their own will. Indoor servants like valets, gentlemen's gentlemen, and dressers. (Dressers are like lady's maids, but of higher rank in the servants hierarchy because they are more highly trained and only concerned with the lady's hair and wardrobe—upon which they often advise her—and don't do more menial, less specialized, stuff which could safely be left in the hands of such lowly individuals—dressers tend to be toplofty, and look down on the lesser servants—as the chamber maids, like serve her breakfast in bed, etc. When travelling one might leave a mere lady's maid at home and make do with a servant belonging to the host's household, but an experienced dresser is too vital to one's image as a person of fashion to be left behind.) Outdoor servants like grooms and coachmen—which may be old family retainers and therefore utterly trustworthy. In mystery novels, there is often a trusted servant who assists the employer to solve mysteries (yes, I am looking at you Lord Peter Wimsey and gentleman's gentleman Mervyn Bunter, but also many who have followed in your mighty footsteps). Why could it not be so in a fantasy novel if the employer is a spy, diplomat, or amateur detective, and the servant is secretly his or her assistant in unravelling vital puzzles? Or if the employer is a magician of some sort travelling in disguise, an apprentice magician might go along disguised as a valet or dresser.
Also, highly qualified servants with good references are always in high demand. Such an individual might change jobs almost at will, and it might put them in high ranking households where important things turn out to be going on. If it was a series, the servant could be with a different employer, in a different city, facing a different set of challenges in every book. Servants see and hear a lot (in part because aristocrats don't deign to notice their presence much of the time) and they gossip together in the servant's hall, so the servant protagonist would surely interact with the other servants a lot in discovering important facts about the situation at hand. Not to mention being the "invisible" person who overhears or observes things his- or herself.