Weird behavior: deleted row still in index?

Hi.

I have deleted a row from a table. Confirmed by "SELECT". All
associated children tables don't have this key value either.

Yet, when I insert this row back again, the primary key index on this
table gives me a duplicate error.

As demonstrated below. PGSQL version is 9.0.5.

Is this common? I have vacuum analyzed the table three times. Still
same problem. Why is the primary key index keeping a value that was
deleted?

Short of a REINDEX (which will lock the entire table....it's a large
one) is there anything I can do to clear up the index?

Thanks!

mydb=# delete from stores where id = '20xrrs3';
DELETE 0
Time: 0.759 ms

mydb=# INSERT INTO stores (id) VALUES ('20xrrs3');
mydb-#
ERROR: duplicate key value violates unique constraint "idx_stores_pkey"
DETAIL: Key (id)=(20xrrs3) already exists.
mydb=#
mydb=#