A search check is called for if they actively search the area containing the little holes (assuming they would find them noteworthy). A spot check is made to notice something you're not actively looking for.
How hard do you want this spot check to be?
My suggestion for setting the DC (for a spot check) is as follows:
Start with a man-sized hole in plain sight (very easy) DC 0.
Modify this up or down depending on the lighting conditions and how well it blends into the walls of the dungeon. (A pitch black hole in a wall of black stone is probably worth a +5 or more to DC, totally your discretion here.)
Apply a size modifier based on the hole's actual size. (See the hide skill for size modifiers, probably +16 for fine = 6" or less, to +8 for tiny = 1' to 2')
If the characters are fighting or otherwise distracted when they enter the room, give them a -5 Spot check modifier.
So a mouse-hole that blends in well with the material in the wall, would be a DC 21 spot check.
If they're on the lookout for such holes, you might consider giving them an extra spot check whenever they enter a new room, if time permits. Extra spot checks cost a move action.
Hope this helps.