Record not returned until index is rebuilt

I have the following table definition in postgres 8.0:

CREATE TABLE "userInfo"
(
  "userID" character varying(32) NOT NULL,
  "password" character varying(32) NOT NULL,
  salt character varying(16) NOT NULL,
  CONSTRAINT "userInfo_PK" PRIMARY KEY ("userID")
) ;

Administrators are able to add new users to this table via PHP web
interface. It works fine most of the time. Every once in a while, we
get a problem where a newly added user does not show up in the list of
all users after being added.

For example, I will add a user named "test" to the database. When I do
SELECT * FROM "userInfo"
I will see that record in the database. However if I do
SELECT * FROM "userInfo" WHERE "userID"='test'
no records are returned.

This record will not show up in the query where it's specified as a
WHERE clause until I REINDEX and VACUUM ANALYZE the table. After that,
the record will show up in both queries. Newly added users will show up
for a while, until the same problem occurs.

Why is it that the record is visible when bulk selected, but not when
selected as a part of the WHERE clause, and why is it that the index
rebuild and vacuum fixes the problem? Is it possible that the primary
key index is not being updated properly?

Thanks.