rcavictim,
When steel melts you can't keep all the little 'magnetic domains' lining up with each, so they will form closed magnet chains within the material leading to an overall neutral magnetic field.
Yes, heating is one way of demagnetising - and no, as you found, you don't need to melt it!
Neodymium magnets are destroyed (magnetically speaking) by much lower temperatures than one might like. I think degradation starts at a little over 370-390 K with these, so be careful with your Neo-PMGs!
Regards, RAB