A lot of modern CPUs (like the P4, I believe) have throttling on them so that if they get too hot then they will slow themselves down to cool off. I don't know if this means that without a heatsink they would still work, albeit very very slowly, but it's an interesting thought, no? ;)
Just found this... seems they do work without fans, just not very well and they do get very hot!
http://www.digit-life.com/articles2/...ing/index.html