How hot can/should an outlet get?
Older receptacles tend to lose their "grip" on the prongs of a plug. Many times this higher resistance connection creates a lot of heat. This is a VERY common problem with dryer receptacles for some reason.

I would definitely change the receptacle. Keep in mind, a 15A duplex receptacle is TWO 15A receptacles on a single device yoke. It is a 20A feed-thru device. So it is perfectly fine, safe and legal to use on a 20A circuit. A microwave would never be considered a continuous load so the 15A actual load is also fine, especially considering the 15A cord plug it has.

It is no problem to use a 20A receptacle, but there is NO benefit other than the prong configuration, unless of course you have appliances that have a 20A plug. In a home this is highly unlikely. 

In high draw areas I like to suggest better quality spec-grade receptacles. They are made with stronger materials and have a much better grip on plugs. In my business I like to use them everywhere in fact. The couple of dollars difference is negligible in the long run.

My personal suggestion would be to change all the receptacles in the kitchen while you're at it and use GFI's at the beginning of the circuits for the countertop areas.