So did you ever get the problem solved, Matt? I certainly hope so. I have a fair amount of experience tracing such problems, and have found hidden GFI outlets, but often I find that a loose or somewhat burnt connection is the problem. If it still isn't fixed, read on.

Turn off the breaker to the circuit and ensure that power is off by either testing with a meter or plugging in an appliance in the known working outlet. Then, pull the outlet cover and remove from the wall, exposing the wiring. If there are two or more bundles entering the outlet (each bundle typically has white, black, bare) then the outlet is midway in a chain of outlets. A single bundle means that it is at the end.

Check that ALL connections are robust. If the wires are poked into little holes in the back of the outlet (backwiring), it should not be considered robust. Remove the wires from the little holes and use the screws on the sides of the outlet.

You might also find that a wire is broken -- when it was being stripped, the conductor was gouged, and when the wire got bent this way and that when it was crammed into the box, it fatigued and eventually broke. Remove the broken-off bit, carefully strip the wire and connect.

If there are three (or more) cable bundles coming together in the box, there are probably wire-nuts holding the connections together (might be tape on top of the wire-nuts), and some little "pig tails" going to the outlet. Check all connections -- the wire-nuts can corrode, break, be loose, or be covering more tape. When reassembling a wire-nut connection, the conductors must be clean, and stripped so that when the wire-nut is installed, the conductors are not easily visible. Personally, I strip about an inch, twist the conductors together, cut off excess conductor to about 5/8", then cap with the wire-nut.

In any case, always make connections to the outlets using the screws on the sides. Insulation must not be under the screws, only bare conductor. The insulation should start within 1/8" of the screw. The bare conductor should be wrapped around the screw in the direction of tightening the screw. Tightened properly, they'll never fail. Unused screws should be snugged.

My guess is that you'll find *(or have already found)* the problem by inspecting no more than three outlets. Then, you'll lie awake at night wondering what condition the REST of the wiring in the house is like...

As mentioned earlier in this thread, a wire tracing device (sometimes called a "toner") is a fabulous tool. I have an Ideal that purchased years ago for phone and data networks, but now I use it mostly for tracing house wiring circuits. Fun to play with!