Are custom Dedupe General rules working for anyone?
It sounds like you might be running the dedupe on a large database with slow MySQL performance; I've certainly seen this before.  The database doesn't even have to be that big; I've seen this on databases with as few as 20,000 contacts.

The pre-set dedupes that can't be edited use a fundamentally different approach to deduping that runs MUCH faster, but it must be hard-coded.

There's an unpublished extension from Veda (see item 1 here; most subsequent items are part of Civi 4.7) that adds a framework for more hard-coded dedupes, along with a large number of extra pre-built dedupes.  That may be better for your situation.  I'm not sure it's tested on Civi 4.7 though, so try it on a copy of your database first!