Referential integrity broken (8.0.3), sub-select help

Hello,

I've got 2 tables, "url" (U), and "bookmark" (B), with "bookmark" pointing to "url" via FK.
Somehow I ended up with some rows in B referencing non-existent rows in U.
This sounds super strange and dangerous to me, and it's not clear to me how/why PG let this happen.
I'm using 8.0.3.

Here are the table references I just mentioned:

Table "bookmark":
id SERIAL
CONSTRAINT pk_bookmark_id PRIMARY KEY

Table "url":
url_id INTEGER
CONSTRAINT fk_bookmark_id REFERENCES bookmark(id)

Problem #1: Strange that PG allowed this to happen. Maybe my DDL above allows this to happen and needs to be tightened? I thought the above would ensure referential integrity, but maybe I need to specify something else?

Problem #2: I'd like to find all rows in B that point to non-existent rows in U. I can do it with the following sub-select, I believe, but it's rather inefficient (EXPLAIN shows both tables would be sequentially scanned):

SELECT * FROM bookmark WHERE id NOT IN (SELECT b.id FROM bookmark b, url u WHERE b.url_id=u.id);

Is there a more efficient way to get the rows from "bookmark"?

Thanks,
Otis