If pressure is proportional to temperature, why aren't compressed gases always hot? When you compress a gas, say within a deodorant can, it temporarily heats up, but then cools to room temperature whilst in the can. It will then cool down to below room temperature once decompressed.
It seems like the gas equation doesn't apply when the gas is cooling down within the can and the pressure remains the same. Does the equation only apply at the instant of compression? It does not apply to liquids, but exactly why does it apply to gases? Also, I have learnt that gases are harder to increase in temperature (require more heat) at high pressures. I can't fully understand why.
Also, can't this concept be used to create a perfect stirling engine? I mean if the gas within the can cools back down to exactly room temperature?
So the question in summary:
1) when and where does this gas law apply and show a proof explaining why
2) why are gases harder to increase in temperature at high pressure, does the same work vice versa?
3) could this in principal make a 100% efficient engine?
 A: When you compress a gas into a deodorant can it does indeed heat up. Then if you let the can cool the pressure falls again. The pressure and temperature will remain related by (approximately) the ideal gas law:
$$ P = \frac{nR}{V}\,T $$
You say in your question:

It seems like the gas equation doesn't apply when the gas is cooling down within the can and the pressure remains the same. (my emphasis)

But the pressure doesn't remain the same while the can is cooling.
For completeness we should note that in real deodorant cans the gas used liquifies under pressure so the behaviour is more complicated than a simple ideal gas.
A: I'll try an answer for the first question.

1) when and where does this gas law apply and show a proof explaining why

The "gas law" you are thinking of is most likely the "ideal-gas law":
$$pV=nRT$$
Ideal, because it only holds for ideal gasses. A gas is ideal when there are no intermolecular interactions. When the viscous effects, electrical and chemical interactions etc. are negligible (no repulsions, attractions, friction or alike). The molecules must be considered point-like and acting as if they were alone in the container.
This is not at all the case in liquids and only becomes approximately true for gasses far from the boiling point / liquid range. Have a look at this pressure-volume diagram (a random one from a quick search that shows the point): 

The left part is liquid, the right part gas. The blub in the middle is a mixed-phase.
Only farthest to the right where the lines (isotherms) become close-to horizontal and equidistant, will the propertionality and the ideal-gas-law be true. If you in this range for example halve the temperature, then the volume is also halved. But pressure remains constant if we stay within a horizontal line, and so temperature and volume are propertional.
The closer you are to the mixed-phase bulb or the liquid phase to the left, the more disturbed the lines become, and propertionality won't hold true anymore.
A: I think the pressure temperature relation that you mention is the equation of state for ideal gas. The ideal gas model is a rather simple model and there're many models and thus many equations of state for real gas. So the pressure temperature relation is not necessarily to be linear. On the other hand, equations of state can only be applied when the system is at its equilibrium, so you simply can't use the equation of state during an irreversible process. To explain why the gas will be even cooler after decompressed, it's better to use the first law of thermodynamics to explain. Because the gas is decompressed, so it will do positive work to the environment, and thus the gas must lose some energy, from dU=CvdT we can see that the temperature must fall.
