First thing I'd check is if the switch is even connected to any wires. You can probably check this just by removing the face plate.
You already checked the receptacles, but did you check both the top and bottom outlet? Sometimes a switch will only control one part of the outlet. In this case, the metal tab connecting both hot terminals is broken so that the top and bottom outlets can be individually powered (and switched).
The next step is to look at the wiring of the switch. First turn off the circuit breaker and test again with a non-contact tester (if you don't know what the switches do, then it could have more than 1 circuit in the box - just to be safe). Remove the switch and take note of the switch type - is it a single pole switch or 3-way switch? (If its a 3-way switch then the color of the traveler might be helpful in finding what it controls.) Is the line (from the circuit breaker) in this box?
If a visual inspection doesn't give you any clues then you need to trace the circuit. This is usually done with the power off using a circuit tracer:
A telecom probe/tracer can also be used in many cases. You hook the tone generator up to the wires at the switch, and then you use the probe to follow the wires through the wall. With any luck you will find your way to a ceiling or wall box. Depending how badly you want to know, you might need to open the wall (or use a scope) at some point to help trace the wire. More expensive versions of this tool exist that might be needed to find really sneaky wires.
It's not unheard of to find out that a previous owner dry walled over an electrical box, so keep this in mind as a possibility.
And if you just can't sleep at night without know where it goes, you could always x-ray your house as a last resort.
(The above image is by photographer Nick Veasey. While this photo was stitched together, there are companies that x-ray buildings )