I'll add to the large (often interesting, but large nonetheless) pile of messages in this thread by remarking that even in permissive mode, SELinux can be very useful as an audit tool.
Those AVC messages folks love to hate show deviations from expected behavior. Sometimes those deviations are false positives and require a policy adjustment or relabeling. Sometimes, however, they show in great detail exactly what an exploited vulnerability did (or tried to do): read or replace files, open TCP ports or sockets, create and populate directories.
A while back, someone exploited a vulnerability on a machine in my care. I'd been having trouble getting other apps on that machine to work and play well with SELinux so I had it running in permissive mode. Using the audit logs, I was able to ascertain with a high degree of confidence the extent of the damage -- using information that would have been unavailable but for SELinux.
Of course, the exploit wouldn't have been possible if I'd been running SELinux in enforcing mode... :-)