I have an over the range microwave that we have been using for 3 years with no problems. A couple of weeks ago it just stopped working, so I just figured it was time for a new one. I replaced the microwave and when I went to plug it in, it didn't work. I checked the breaker, it had not tripped, so I plugged It in to another outlet and it works fine. I thought maybe the outlet needed to be replaced so I replaced it, still no power. The oven runs off the same breaker, it works fine. I'm out of ideas
Look for a GFCI outlet upstream that has tripped. Kitchens are full of them, but they also turn up in non-intuitive places like bathrooms, laundry rooms, beside electrical panels and garages.
Oh, and I just remembered that some breakers can have tripped without looking tripped. If the gfci trick doesn't work, go through your panel and turn each breaker off and on.
(Added to this answer b/c comments...)
If all that doesn't work, there's some circuit investigation needed. I'll let you decide if this is the kind of work you want to do or hand off to a pro. Some of this involves meters and live wires, so caution is appropriate.
Get into the microwave junction box and verify with a voltmeter that there's no current flowing.
I know you said the oven is on the same circuit and works, but humor me and start at the panel. (Danger alert! Open panels are hazardous! Main power off!) Check the connection of the microwave circuit to the breaker. Check that the breaker is seated properly. Temporarily move the microwave wire onto a different (but same amperage) breaker to see if it was your breaker that failed. (Please tell us if your breakers are Zinsco or Federal Pacific.)
If you seem to be getting power out of the panel into the microwave circuit, then some work follows. You'll need to follow the wire from the microwave junction box on its way back to the panel. (You might be lucky and find that the first one is just below at the stove and that the issue is located there.) A tone generator (under $100) will help a lot. (Most inexpensive tone generators want the power to be off, so strongly suggest you turn off the whole house when you're tracing.)
You need to identify every junction box that the wire goes into and hopefully find a disconnection. Look for loose wire nuts, burnt smells, charred wire... anything out of the ordinary. In an ideal world, you'll find a bad connection and be able to fix it. Otherwise, you'll have found a stretch of wire where one junction box is live and the other is dead. (Sadly, there are cases where people (jerks!) bury junction boxes or connections under drywall.) It's rare but possible that wire in the wall has been broken -- vermin chewing, or a nail that partly broke the wire that's finally failed.
At this point, you want to be careful that you've accurately mapped your wiring, but you're probably in need of a new section of wire from the live junction box to the dead one. I'd seriously consider calling in a pro at this point to make sure everything is correct.