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