The classes behind matching, notifications, online lists and search had grown over years into long methods with many branches. phpmd flagged methods with cyclomatic complexity over 10, and one search method had 12,288 possible execution paths.
Code like that is hard to test and risky to change, and these classes changed often.
What I did
Took one class per ticket, about 20 classes in all, instead of one big refactoring, so each change was small enough to review and release on its own.
Used the team's phpmd thresholds (complexity 10, 200 paths) as the definition of done.
Split long methods and large classes into smaller ones, and removed dead code: unused methods, parameters and variables.
Removed an obsolete online-users class and moved its callers to the newer one.
Ran the tests with every change, fixed the ones the refactoring exposed and added tests where a bug turned up.
Result
About 20 classes, one per ticket. Team limit: 200 paths; one method had 12,288.
The classes my 22 refactoring tickets covered, each compared before my first and after my last commit.
Measured on the code itself (no production data): each file exported from git before and after, then analyzed with the project's own PHPMD 2.15 and PDepend at their default thresholds.