I'd first check if someone incorrectly wired a single half switched receptacle. To do this, you're going to need to check the outlets for a hot and then determine how the circuit is run through the walls for the switch.
Turn off the switch and check outlets to see if there's still a hot connection anywhere. I'd try with a non-contact tester first, and if that fails, shutoff the power, pull the receptacle and wiring out of the affected outlets to make them more accessible, and turn the power back on to test again.
If you locate an unswitched hot in an outlet, disconnect the receptacle from the wiring with the breaker turned off, and then turn the breaker back on to identify the switched hot wire (toggle the switch on and off to see what wire toggles with it). If other outlets show no power when the receptacle is disconnected and the switch is on, you've got all the wires there to change the receptacle to 1/2 switched (broken off tab between the hot terminals) with the load connection made to the unswitched hot.
If other outlets have power when the receptacle is connected and the switch is on, then you need to disconnect other receptacles to locate the source of the switched power. Once located, you'd wire that receptacle as 1/2 switched.
Standard disclaimer: If you're not comfortable with electrical wiring, don't have the proper safety tools, or don't understand how 1/2 switched receptacles work, you may want to hire a professional to do this. Testing wires for hot needs to be done with the breaker on, but otherwise always have the breaker off when working on electrical wiring.