Guarantee uniqueness of PGP key

Hi,

More generically, how do I best guarantee that any large varchar is unique
before inserting?

In my application, I need to ensure that each e-mail address and
corresponding PGP public key are both unique.

I originally implemented this by adding a uniqueness contrainst to both
columns.  easy.

The problem is that some PGP keys are over 2713 bytes, and postgres (7.2)
gives the error:

ERROR: btree: index item size 4336 exceeds maximum 2713

I thought perhaps I could use a hash or rtree index, but neither of them work
for unique-ness.

I saw in another posting that it may be possible to raise this limit to 8k or
so, but I don't want to do this because 1) it requires a recompile of
postgres (and rollout to dev, stage, prod machines), and 2) a key could
theoretically be longer than 8k anyway.

I can guarantee unique-ness by removing the index and doing a select before
the insert.  If there is a matching row, then I am trying to insert a dup.
bail.

My concern is that doing this without an index will be monumentally slow for
any large-ish number of keys.

Any bright ideas? All suggestions appreciated.

/andre