TypeUKinUSA hit it dead on. The reason combustion temperatures are reasonable in a car is due to the fact that the air is mostly N2. But, if you have a pure hydrocarbon and oxygen flame, the temperature can sky rocket and you can have molten metal. Think what an oxy-acetylene torch can do to your engine block. Acetylene is a simple hydrocarbon, C2H2...
So, this brings up a major reason that people use NOS; it has two nitrogen molecules for everyone one oxygen molecule. Nitrogen is a great diluent since it has a large heat capacity. As the NOS expands from high pressure, it's temperature drops considerably (anyone use compressed air bottles to clean their comuter?) and it cools the intake charge, making it more dense. So, even though N20 is only about 36% oxygen by volume, you can cram even more N20 in, thus more oxygen in.
Like everyone else has said, pure oxygen would be great, but it's too hard to handle safely.