Hi-tech, some queens are more shy or smarter or perhaps both. When searching for her, she will be where the most bees are on the brood comb.
I use my bee vac when I need to. I find it works best on hives with large numbers, but if the hive can be dealt with without one, I just cut the comb out and place it in the hive body. About the mess, I remove the honey comb first, then brood comb, but it does'nt always go this way. If for some reason, by cutting the honey comb, you will spill onto brood, then cut out the brood first. With so few bees, you can do what Brian suggested. Have fun.