lazy vacuum and AccessExclusiveLock

Hello,

we are facing strange situation with exclusively locked table during
normal lazy vacuum. There is one big table (66GB) that is heavily
inserted and updated in our database. Suddenly (after backup and delete
of almost all records) we are not able to run VACUUM over this table
because after 50 minutes of work it allocate AccessExclusiveLock on this
table and all other connections start to timeout.

It's common knowledge that VACUUM doesn't block and it looks like it's
not true. I found this little excuse in documentation
(http://www.postgresql.org/docs/8.3/interactive/routine-vacuuming.html):

"... it does not attempt to reclaim the space used by this dead data
unless the space is at the end of the table and an exclusive table lock
can be easily obtained. Unused space at the start or middle of the file
does not result in the file being shortened and space returned to the
operating system."

This seems to me that situation can appear that dead tuples are in such
position that VACUUM will decide to reclaim free space and block other
process! Is it true?

I found old thread in archive speaking about similar problem
(http://archives.postgresql.org/pgsql-performance/2008-06/msg00235.php)
but with a resolution that it should be no problem any more. It looks
like it is still a problem.

If this is true, is there any solution how to convince vacuum not to
reclaim free space in any situation?

Regards,
Jaromir