PostgreSQL 9.0.4 blocking in lseek?

We are running into a significant performance issue with
"PostgreSQL 9.0.4 on x86_64-pc-linux-gnu, compiled by GCC gcc-4.4.real
(Debian 4.4.5-8) 4.4.5, 64-bit"
(the version string pqAdmin displays).

A fairly complex insert query on an empty destination table will run for
an indefinite amount of time (we waited literally days for the query to
complete). This does not happen every time we run the query but often.
Now ordinarily I'd assume we did something wrong with our indices or
query, but the execution plan looks sane and, more tellingly, we have:
- no CPU load
- no network traffic
- no disk I/O
- no other load on the server except this single query
and strace displaying a seemingly endless list of lseek calls.

So my assumption is that we are not running into bad Big-O() runtime
behavior but rather into some locking problem.

Any ideas what might cause this? Workarounds we could try?

thank you,

Sören