Remember that a search party would not be like what would happen today. There's not so many goblin ambushes lurking for groups of civilians in a fair portion of the modern world. Search parties could be an order for a militia squad. If the game remembered what map tile / biome the dwarf / creature was last seen in, there could be an order like
kill - Search, select searchee, squad goes a-wanderin' in that area, staying near each other in case some nastie got the missing fellow and comes back for more.
As for slabs, unless the ghost rises up, or you find/are attacked by the corpse, perhaps there's a time limit, after which the fellow can be declared dead? A few years would not be unreasonable - whether he's actually dead or not, doesn't really matter.
Going off on a tangent, the notion of bounties intrigues me. If someone is killed / eaten / kidnapped, they're missing. What would make a dwarf run away from the fortress? The vampire stuff brings in witnesses and the like. Imagine a murder is performed, but not witnessed. Eventually, a body is found - stabbed with an short sword, says the medical dwarves. A few days later, one of the fort's three short sword owners sneaks away, taking food, booze and some coins / jewellery with her. If the player or the victim's loved ones could put up a bounty for the capture. Eventually, this might bring in adventurers who accept the offer of gold or reputation for hunting down bandits and criminals. It'd be kind of cool having a fort, "retiring" it and coming back later as an adventurer to help them out.
Back on topic:
I don't think the multi-group suggestion is a good one. It seems like it wouldn't add much fun to the game while being irritating to implement and use. 'Missing' dwarfs who wander around and do things could completely mess up FPS and throw off the ability to control labor assignments (and keep calculating their 'missing' status).
If 'missing' dwarves still keep their old labor assignments, but can't be seen, then what happens when they start getting moody and grab an out-of-the-way workshop? Or when they decide to take a job? Hopefully they'll be spotted soon, but especially in large forts there's a lot of out of the way corners. And FPS is a huge problem already, we don't need to add more random, uncontrollable ways to sink it.
A better way would be to simply reset a timer every time a dwarf sees another dwarf. C'mon, most forts never get above 100 people, you think the dwarfs don't know everything about everybody? These are tiny, tiny villages, not large cities. It's uncommon for people in really small places to go missing and not be dead/out-of-the-area.
A valid concern, sure, but I can't see how the removal of multiple groups fixes it.
To clarify, you mean a global timer, or one per dwarf? If the former, that would basically dissolve the whole concept. If the latter, I don't understand how this is different from what has been suggested already. A single dwarf can grab a workshop as well as six can.
As for "irritating to use", as I suggested it, there's nothing to use - if multiple dwarves go missing, it happens, and the only away it affects the player is if one wanders back in (telling you where the others are), or if they stay away long enough to become a different group within the civilisation, in which case they
really don't affect you any more, and have't for some time. I may be missing something, but that particular objection doesn't seem to hold water.