strange bug with vacuum

Operating system:
Linux (PLD), kernel 2.2.20

Hardware:
$ cat /proc/cpuinfo | grep -E "^(vendor_id|model name|cpu MHz)"
vendor_id : GenuineIntel
model name : Pentium III (Coppermine)
cpu MHz : 871.474

$ free
total used free shared buffers cached
Mem: 387712 385028 2684 79864 146396 179892
-/+ buffers/cache: 58740 328972
Swap: 524624 0 524624

PostgreSQL version:
PostgreSQL 7.2b4 on i686-pc-linux-gnu, compiled by GCC 2.95.4

it appears that doing vacuum analyze just after creation of tables and
indices permanently damages indices.
our code made something like:
create table();
create index ..
vacuum analyze;
now apporximatelly ca 100000 inserts, each prepended by
select id from table where field = value;
field is of type int8 (value also, and we do casting to int8) and there
is unique index on table.field;
every 5000 inserts we do vacuum analyze of this table.
the problem is that the time system spends on mentioned selects raises
linear way instead of (expected) logarythmical.

we checked twice that *not* making initial vacuum (while still doing
vacuum analyze every 5000 inserts) does modify this behaviour to much
more reasonable.

is this something we are missing or another bug in postgresql?

the selects and inserts are made through plpgsql function (single call
select function(args) does select and insert), but i doubt if this
matters.

depesz

--
hubert depesz lubaczewski http://www.depesz.pl/
------------------------------------------------------------------------
... vows are spoken to be broken ... [enjoy the silence]
... words are meaningless and forgettable ... [depeche mode]