Contact Dedupe Basics
Dedupe exceptions are those contacts that have been flagged as potential duplicates, but someone clicked the "Not a Duplicate" link next to them.  If you remove the exception, they can be considered duplicates again.

CiviCRM has two kinds of dedupe rules - those that you build and some pre-built rules that give much better performance.  Many of the default supervised/unsupervised rules are pre-built rules.  The rules you're building are timing out.  To deal with this, try increasing the server's PHP timeout or reducing the complexity of your rules.  Also - dedupe has received a lot of love in recent months, so consider upgrading CiviCRM to the latest 4.7 for a performance boost.

If you're handy with SQL and want to write a "pre-built" dedupe query, the hook is hook_civicrm_dupeQuery.  Veda's dedupe extension is outdated and may not work on current versions of CiviCRM but has a large number of high-performance dedupe rules.