Hi Scott
My initial guess after reading your post was:
Are Duplicate Detection rules get affected by import of solutions or customizations.
I wasnt sure about it so did a bit of search and found this post:
Try it and conclude if this is the reason in your case as well
http://www.madronasg.com/blog/duplicate-detection-rules-automatically-unpublished
This is for CRM 4 but can be a valid reason for ur problem
Also if it helps you, kindly confirm so that it can help others