Power Interruption/Outage: Outlets, Basement, Stove/Oven and Furnace
Number 4 is the big clue. One side of your electric service is dropping out, turning on the stove causes it to back feed. This is likely caused by a loose connection on one of the service lines feeding your house.  There are however a few other possibilities I'll cover below.

For the sake of explanation, let's say the location of the problem is a loose lug inside your electric meter.  Over time that loose connection has been building up heat, it's likely aluminum wire that melts and burns and produces black carbon. As this continues over time it eventually works its way "open" and will no longer feed that side of your electric service resulting in partial lights out in your house, that might mysteriously just come back on as that burning lug cools down. You turn on the stove (which uses both sides of the electric service) and it back-feeds current through the circuit back to that bad lug, when that happens and the two opposing sides of the electric service meet it arcs and it can actually create a weak "weld" of sorts, restoring the power again, until the connection once again burns open. repeat.  Eventually it will just burn open and be broken until someone finds the problem.

Connection points on the power companies side include the pole (or underground connection vault or stump), and the meter can, and possibly an outdoor disconnect.  Most often in our area the problem is one of the meter lugs was not tight.

On the customers side, where the service feeders connect to the main breaker inside your panel is also a place for a possible loose lug. (In my area the power utility will actually tighten main lugs in the customers panel, many utilities however will stop at the meter.)  Beyond that it's also possible there is a problem with the main breaker or panel buss itself, but that's less likely (IMO) than all the above. 

Start with a call to your power company and report "intermittent partial light out". They will check connections outside your house and may even check your panel for loose feeders. They also may not check past the meter, in that case you would need an electrician to check your panel for loose feed--if the power company didn't solve the problem outside. 

Most electric utilities don't charge for the service call for their side, if it is your equipment in the end, you will of course have to pay an electrician for their work.