How do relay contacts survive inrush current?
Relays aren't perfect switches, and will have a certain contact resistance, which may be several tens of milliohms. In power applications this has to be taken into account. A relay with a contact resistance of 10m\$\Omega\$ carrying 16A will dissipate 2.5W in the contact!
It has been suggested that contacts tend to weld more on opening than on closing. I don't think that's correct. Firstly, in most relays release time is much faster than operate time. Secondly, yes there is often a nasty arc when opening, but that arc is actually a sign that contact anode and cathode are in fact separated, and then they can't weld anymore. That doesn't mean that arcs are harmless. They're a powerful HF transmitter and cause much EMI. And they burn the contact's coating. In AC switching they will extinguish on the zero-crossing, after maximum 1/100 or 1/120 second (doesn't count for very high voltage switching), but in DC this may take longer. That's why DC ratings for a relay will be significantly lower than AC ratings.
So contacts tend to weld upon closing, and you rightly mention that the contact resistance isn't minimum yet during the inrush, so it looks strange that exactly then a higher current is allowed. It's all to do with time. Closing a contact usually takes several ms, but most of that time is used to build the magnetic field in the coil and the travel of the contact's anode also takes some time. The actual time between first contact and final closure is very short. Add to that that the current isn't 80A yet at the first contact; current can't go from 0 to 80A in a nanosecond. So while the current builds up, the resistance decreases. All in a very short time, so that the total dissipated energy in general won't be too high.
For situations where this isn't good enough there are relays with a separate faster tungsten contact to improve closing performance. (In Dutch it's called "voorloopcontact", I don't know the name in English.)
edit (in reference to comments to different answers)
There was some discussion whether the relay would weld upon opening. Steve quoted Siemens: "[welding occurs upon] opening and immediate reclosing of contacts". If you want to weld the contact this is definitely the way to do it. Opening will probably draw an arc, and reclosing it during this arc means that there's current during the high resistance phase at the first contact. Contact + high energy = high risk of welding. Even if the arc already extinguished the air in the gap may still be ionized, meaning that it may breakdown during reclosing before contact is made, and that there's already current when closing. So basically the same situation.
Further reading:
Tyco application note: Relay Contact Life
The effect of high currents is to heat up the metal. The resistance of the metal converts electrical energy into heat energy. If the current spike is very short, the thermal energy is not as great, and it can be dissipated before it melts the metal.
It is the current that the relay has to interrupt that you need be concerned with. That is when the contacts tend to weld.