I am planning to upgrade postgres to avoid this autovacuum problem.
From the release notes of postgres-8.1.x it seems this issue has been solved in postgres-8.1.6 and hence upgrading to latest 8.1 release i.e 8.1.21 will solve this issue.
But I was just wondering if postgres-8.4 will also be having this fix (as I couldn't find it in release notes of postgres-8.4).
8.4 has much better autovacuuming, seeing as it's multithreaded and you can have a lot more control over how it behaves. This fix is definitely in 8.4 and 8.3, or should I say the bug you hit was long gone by the time the 8.4 branch was cut.
OP: Do be aware that if you jump straight to 8.4, there are some incompatibilities that may require changes to your code. The one people seem to be bitten by most frequently is the removal of implicit casts to text:
... but, in general, you should read the release notes for each major version and see if you need to change anything to achieve a smooth upgrade.
I think, from the beginning the OP has been unaware of the fact that upgrading to latest minor release does not require a huge effort, and that it involves very low risk of breaking any applications, Slony or otherwise.