Vacuuming on heavily changed databases

Hello,

I would like to ask an opinion on vacuuming general. Imagine situation
that you have single table with 5 fields (one varchar). This table has
during the day

- cca 620 000 inserts
- 0 updates
- cca 620 000 deletes

The table is vacuumed daily, but somehow after several months I got to
size of ~50GB

Result of VACUUM FULL VERBOSE ANALYZE is:

Nonremovable row versions range from 102 to 315 bytes long.
There were 218253801 unused item pointers.
Total free space (including removable row versions) is 40627058888 bytes.
4850610 pages are or will become empty, including 0 at the end of the
table.
5121624 pages containing 40625563500 free bytes are potential move
destinations.
CPU 161.85s/35.51u sec elapsed 1191.17 sec.

This means 80% wasted space that could be reused. Right now, I am doing
vacuum full but this requires exclusive lock. During that time the
database is locked so I am missing "inserts and deletes" ;-)

I would like to avoid this in future, so I would like to prepare strategy
how to do it next time or avoid. Basically I have the follwing
limitations:

1) sometimes deletes vs vacuum analyze does not help, extra space is not
relcaimed. Do not know why this is happening, but maybe vacuum cannot get
lock

2) manualy evoked vacuum full requires bringing database long-time offline

3) There were suggestions (in archives) doing dump and then restore on
dropped database, but still requires downtime.

What would be your strategy for the database maintenance like this? What
tweaking of vacuuming can I make, so I do not get those "forgotten"
records?

Thank you,
Bohdan