Lyle pointed out another problem with how CPANdeps detects distributions that contain both XS and a "pure perl" alternative implementation. Some distros name the pure-perl implementation Blah::PP or something similar, instead of Blah::PurePerl. Unfortunately, PP can mean a few other things too. The only way to get this absolutely right is to manually examine all distributions that look like they might contain some non-perl code, so rather than do that and build a database that the application can use (a database that would go out of date overnight), I took the lazy route and just wrote up some explanatory notes on exactly how the "purity" option works.
For authors who want to help my heuristic show the right result for your modules, then all you need to do is include the string "pureperl" (it's case-insensitive) in your MANIFEST file.