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.

Complementing other answers …

---

Observe verbose mode during restart or shut down

Mac OS X: How to start up in single-user or verbose mode

– if you start in verbose mode, then restart or shut down will be similarly verbose.

Hint: if things in verbose mode seem to not progress beyond a certain point, allow maybe five minutes before either:

• forcing a restart (Command-Control-power); or
• forcing a shutdown (press and hold the power key).

If a forced restart does not succeed, that could be another clue to the cause of the problem(s).

A related question, albeit not problem-oriented: Can anyone interpret verbose shutdown messages?

The problem-oriented case here should be easier to resolve for lupincho. Fewer tea leaves.

To start in verbose mode without keying Command-V

A preference can be stored in NVRAM. Enter the following command in Terminal, and be prepared to enter your admin password:

sudo nvram boot-args="-v"

The next start of the system will be verbose.

---

sysdiagnose

Before each restart or shutdown, in Terminal:

sudo sysdiagnose

It's time consuming, but you need not investigate the results of all runs. Pay attention only if a problems arises.

For a case such as lupincho's:

• the run of sysdiagnose may reveal a problem before a restart or shut down
• the end result of sysdiagnose may be of interest following a forced restart or shut down.

More specifically: if a run of sysdiagnose fails to progress beyond a certain point, knowing that point can help to gain a sense of the underlying problem.

During the run you can use the following key combination, repeatedly, to see whether things are progressing:

• Control-T

For the allmemory part of the sysdiagnose routine, Apple's two minute estimate may be wildly inaccurate. Be patient.

If you suspect that sysdiagnose fails to progress beyond a certain point, then key:

• Control-C

If repeated use of Control-C fails to abort sysdiagnose, then (in my experience with Mountain Lion) it's almost certain that an attempt to restart or shut down the operating system will fail.

---

Shutdown monitoring

In Finder, go to:

/private/var/log/shutdown_monitor.log

This file is typically empty, but may contain items of interest following a problematic shutdown. (I have little experience in this area.)

If the only stray process at shutdown is WindowServer

It's not unusual to have stray processes at shutdown. A stray can be problematic only if it is not killed.

If you suspect that WindowServer is not killed, and that this particular stray is contributory to shutdown failure: ask yourself whether any third party software makes nonstandard use of the WindowServer process.

Quick Look of a GrabFS view of WindowServer on Mountain Lion, with two displays:

If Lion is similar, then my gut feeling is that the cause of shutdown failures lies beyond WindowServer.

---

Guesswork, based upon results of launchctl

Whilst the machine is running normally, what response to the following command?

sudo launchctl list | grep  --invert-match com.apple

Wonder whether any non-Apple software is contributory to the problem. Anti-virus, anti-malware software?

---

Following an upgrade from Lion to Mountain Lion

Aim for:

/private/var/log/com.apple.launchd/launchd-shutdown.system.log

It seems the default is one log per shut down, with a maximum of two so there's also:

/private/var/log/com.apple.launchd/launchd-shutdown.system.log.1

Following any forced restart or forced shut down, you might choose to set aside a copy of the most recent of the two. If force is required on any more than one occasion, you can compare files to see whether a pattern emerges.

Generally

Don't rule out the possibility of an issue with third party software, even release quality. Little Snitch may be well written and widely respected but:

• when problems such as the one in this question become extended or too puzzling, any non-Apple kernel extension deserves attention.

I tested Build 12A269 of OS X 10.8 for around two weeks before it was released, with particular attention to shut down behaviours in difficult situations. Whilst I have not watched any videos from WWDC 2012, I do have a sense that Apple has worked very hard to prevent the need for force in all but the most difficult situations.

Building upon David DelMonte's answer

At least on Mountain Lion, I see the load of Little Snitch 3.0 Preview 2 (3857) very early – before shutdown logging begins. If things relating to this KEXT are similarly late around shutdown time, then maybe an issue will be not evident in the usual log files on disk.

---

If ever you discover the cause of the problem – with either Lion or Mountain Lion – I'll be pleased to know.

In the meantime, with big thanks for the bounty, a closing thought:

kextstat -l | grep --invert-match com.apple