You might try the approach the NCBI uses in the PGAP pipeline: BLAST all proteins against a central database. If two adjacent proteins hit one larger protein in the database, this pair is flagged for closer inspection.
From my experience, this usually results in 10 to 20 candidate pairs in a 3 Mbp genome.
Many people say they exclude psuedogenes from their data sets by looking for nonsense codons and stop codons in their sequences. I don't think that's the best way, but it's certainly something people have been doing for a while now.