What happens to a logic gate (besides magic smoke discharge) seeing a voltage greater than Vcc? Is it just because the gate was not designed to handle a higher voltage than the recommended Vcc, or is it also usually important to limit the voltage to the actual Vcc even if the chip works within a range of voltages?
It's the actual VCC that matters.
Logic gates (and microprocessors) have a diode to VCC and a diode to GND at every input and output pin. (Except for a few chips that have a few "high-voltage tolerant" open-collector pins, as pingswept mentioned).
If you externally drive an input higher than the actual VCC at the time, current will flow through that diode.
As long as you limit the current through that diode below the maximum current listed in the datasheet, slight over-voltage won't do any permanent damage. However, even when limited to very small amounts of current, this is enough to disrupt analog circuits on the chip -- the digitized value from an ADC reading one analog input pin can be totally wrong when it is upset from a voltage slightly above VCC on some other pin.
seemingly small currents through that diode can locally over-heat the region on the chip around that pin, destroying functionality associated with that pin. A person can spend days trying to figure out why his software seems like it mostly works OK, except for stuff connected to that one pin. (Guess how I know this?)
slightly larger currents through that diode can overheat and destroy the entire chip.
Almost every IC you can buy has a number of "hidden features" that are assumed to be present and thus not discussed in the datasheet.
Among these are body diodes/ESD suppression diodes. These guys generally hide on every I/O pin on every device, from basic logic gates through memory to high-end microprocessors. They route any voltage that is greater than VDD (supply voltage) or lower than VSS (supply common) to the appropriate rail.
If you apply a voltage in excess of either of these limits, the body diodes become forward-biased and effectively clamp the level at the pin to either VDD or VSS. This sounds like a good thing and generally is, but they are very small devices and cannot dissipate much power. You can end up damaging this diode (shorting it or blowing it open). In the former case it can lead to "stuck" I/O pins, and in the latter case, the next overvoltage can destroy the input.
Open-collector outputs are handy for being able to control some outputs, as pingswept mentioned already. Putting small resistors in series with inputs which may come into contact with nasty voltages, and/or using external diodes (even an 1N914 is HUGE compared to the protection diodes on the IC itself) is a good way to help protect devices.
Of course, properly designing your input or output circuitry to handle continuous or repeated transient events like these can be a design challenge in and of itself. Generally speaking, if you are worried about blowing an expensive part, buffer the input or output with (much) cheaper and preferably socketed buffer ICs.
Two issues: Protection diodes from an input to GND and VCC will allow large currents if the voltage at the input is above VCC or below GND. Eventually, the diodes might heat up a lot and become low-ohmic, i.e. they will act like a short from the input to VCC or GND. Also, latch-up may occur. This means that a parasitic thyristor hidden inside of the IC's input circuit will turn on and remain turned on as long as the external voltage is present and causes a current to flow into the input. Eventually, the input circuitry might heat up and permanent damage will occur.
There are two things to watch in the data sheet: input voltages relative to the actual VCC applied to the chip (they read something like V_in must be less than VCC+0.3V and greater that GND-0.3V) and absolute voltages at the input pins (e.g. V_in must be less than 6V). Exceeding the limits relative to VCC will likely blow the internal diodes. Exceeding the absolute limits will likely blow the gate of the CMOS transistors at the input.
Some logic gates designed for interfaces between 3.3V logic and 5V logic can handle 5V at the input when the IC itself is supplied with 3.3V, but these are rare. These ICs lack the protection diodes from the input to VCC (and usually have z-diodes from the input to GND and some other tricks to prevent ESD damage).