Why does my Mac Pro running Snow leopard freeze on blue screen on shutdown?
Seems like the problem persists even after many trails of fixing it on different levels. The title is about the problem and the rest is just details of many possible solution that didn't work.

I'd suggest looking into the system.log file to start with. Specially before the last boot-up and after the last freeze points.

If nothing is a suspect of causing the problem in the system.log, then it might be some third-party extension/daemon that is the cause of the problem.