So an overlord wants to create his own floor guardians and maids. The question would have the overlord's created creature obey unquestioningly the creator's wishes but not have this obedience due to a magical effect. Further, the created creature must possess an Intelligence score of at least 3, be able to advance by class level, be able to heal on its own, and possess more than 15 Hit Dice. I'm also going to assume that it's best if the created creature looks as close to a normal humanoid as possible. All that being said, I don't think any one created creature meets those criteria: that's just too big of an ask. However, a creator can get awfully close.
Effigy humans with rudimentary intelligence
An overlord that's at least level 12 and that possesses the feat Craft Construct (Monster Manual 303) can pay an extra 8,000 gp when creating a construct so that it possesses the natural ability rudimentary intelligence (Dragon #327 73). This gives the construct an Intelligence score of half its creator's caster level, yet the construct's obedience to the creator remains intact.
The presence of an Intelligence score grants the construct skill points and feats. Ask the DM who picks how such a construct's skill points are spent and what feats the construct possesses. Chances are good that the construct's creator will be allowed to pick, but a DM may himself pick, perhaps by accounting for the presence of a construct's animating spirit, which is, to be fair, sort of like an NPC, I guess. (Also see this answer for more on the animating spirits of some constructs.)
If that construct's Intelligence score is at least 3, the construct is eligible to advance by class level (also see this answer) and may gain a language (MM 7 and here and also see this question). (The construct's Intelligence score will be at least 6 what with the prerequisites that the creator must meet to grant the construct the rudimentary intelligence feature in the first place, but whether the creator can pick to create the construct with a lower Intelligence score is something to discuss with the DM.)
Although a creature that possesses the template effigy that's created with the feat Craft Construct is made "from wood, leather, metal, and wire" (Complete Arcane 153), its "true nature is not always immediately obvious. Some are quite lifelike, revealing their true nature only after taking serious damage" (151). When "serious damage" occurs—and, yes, the original is actually that vague—, observers make Spot skill checks (DC 20) with success meaning that the observer knows that the creature is an unliving automaton. In other words, even without a mundane disguise or magical aid, an undamaged effigy human, for instance, probably looks pretty much like a normal human.
Thus, according to the rules in Complete Arcane, an effigy human that possesses the feature rudimentary intelligence is unquestioningly loyal to its creator, possesses an Intelligence score of at least 3, and can advance by class level. When the effigy creature gains either the feat Craft Construct or the skill Knowledge (architecture and engineering) (10 ranks), it can repair itself of 1 hp of damage by taking 1 hour and spending 50 gp. (The effigy creature possesses the type construct (MM 307) therefore it can't heal on its own, and spells like the 1st-level Clr spell cure light wounds [conj] (PH 215—16) et al. won't work on the construct as the spell's description says that it only heals living creatures, this sad fact going unmentioned in the cure spell's Target entry.)
The bummer? An effigy creature "[d]rop[s] any Hit Dice gained from class levels (to a minimum of 1) and change[s its] remaining Hit Dice to d10s" (CAr 152), so an effigy human is always created with just 1d10 HD. Luckily, the Dungeon Master's Guide on Other Statistics for Monsters, in part, says
Creatures with Hit Dice of 1 or less have normal, class-based Hit Dice and features. They get a feat for their first class level and multiply the skill points for their first class level by four (even if they have a level adjustment). Those with 2 or more Hit Dice have statistics based on these Hit Dice plus Hit Dice for class levels (if any). (172 and emphasis mine)
As with the construct's feats and skill points, who determines what class level is gained by a newly created effigy human that possesses the ability rudimentary intelligence is up to the DM, but if the DM doesn't institute a house rule like A creature takes levels of commoner unless otherwise noted—and, since it's never otherwise noted, nyah-nyah! then the creator can probably pick. At any rate, a wise overlord will demand his created creatures make runs through an increasingly challenging series of nonlethal traps of his own fabrication—his peons' personal peninsula of power leveling, if you will. In short, although the overlord can't produce from the get-go high-level effigy humans, with the proper setup the effigy humans that he creates won't remain level 1 for long. (The Dungeon Master's Guide explains all about traps (67—76) and how creatures earn XP from them (39).)
Each typical level 1 effigy human that possesses the ability rudimentary intelligence costs 12,000 gp to create and expends from the creator 480 XP. A level 12 PC typically possesses wealth enough to have created seven of these, but a level 12 NPC only enough wealth for two. However, if this is a mastermind-style NPC, he can have whatever machinations the DM says he has that permit him a nigh-infinite supply of such minions.
Finally, be aware that introducing to the campaign the template effigy brings with it some risk. For example, a creator can apply to a human first the template half-dragon (MM 146—7) then the template effigy, increasing the resultant created creature's ability scores and granting it some special abilities but at no increased cost. That is, because the effigy template increases in cost based solely on a creature's size and HD, any number of templates can be plunked onto the creature so long as the templates leave the creature's number of HD and size unchanged and the creature's type is still legal for the effigy template. Once the players learn of this, the DM may have to put a stop to it. It's one thing to create an effigy human fighter 1, another thing to create a half-dragon effigy human fighter 1, but something else altogether to create—in order—a fiendish half-fiend half-gold dragon celestial effigy human fighter 1. And that's with a fairly conservative reading of the Monster Manual. (One more liberal reading would allow the template half-dragon to be applied once for each dragon variety!) Anyway, this DM recommends some thought be given to limiting an effigy creature's ability to accumulate templates prior to having the effigy template applied.
Note: I was unfamiliar with the Overlord intellectual property prior to the question. After some discussion with my son (who was enthusiastic but familiar with it only through pop-cultural osmosis), I ordered a few seasons of the anime; we'll watch it during his Winter Break. Thank you for the oblique recommendation.