We just went through something similar, but much more dramatic.
Lost power on the curb side shortly after moving in to the home when I plugged a vacuum into an outlet I hadn't used before. Lights on that side would flicker sometimes or not come on at all. It took me quite a while to figure it out because on this same circuit we had a really old window AC that was popping the breaker if the switch was set on a particular setting, confusing the issue.
After doing some extensive troubleshooting, I discovered that all the power on that side was on one phase of the 220. I isolated the problem by pulling the breakers off of the phase that didn't work (leaving wires attached) and plugged them into the other phase - then the curb side worked. Called the power company TWICE. Each time they came out they pulled the meter out and placed a load on it that they said was like running 3-4 MHs and all looked good.
My electrical setup is a little different than average, in that it 'plugs in' to a box with a large 4 prong plug (similar to an RV plug but a little different). Between that box and the meter is another box with two big blade type 150amp buss fuses (about the size of toilet paper rolls) which is then wired to the meter.
The second time they were out, I got the manager involved and the power company guys were more thorough (even though they are not responsible for anything 'downstream' of their meter). They opened up the box that my home plugs into and started wiggling wires while having a hand-held meter reading the voltage. When they wiggled the wires on the back of the plug receptacle, the voltage swung wildly, from 120V down to as little as 40V. They recommended rebuilding that box.
My manager replaced that box (and even built me a new 'cord') and there was no change. My manager then opened up the big box with the fuses, and found that on one phase coming in from the meter on the upstream side, the set screw and lug was wobbled out and loose. Evidently, when the power guys were wiggling the wires on the back of the plug they were also wiggling the power pole (the ground was saturated from rains and the wooden pole was loose in the ground) and the pole wobbling was causing the bad connection in the fuse box to wiggle around as well.
My manager shimmed the connection by using a large solid copper wire folded in half and then stuck into the lug with the cable going to the meter so he was able to tighten down the set screw. Worked like a charm.