Personally, I am no longer a fan of optional dependencies*, because they tend to complicate things in exactly the way you describe. I would suggest thinking about alternatives, such as just deciding to either declare the module as a dependency, or removing it, perhaps a replacement is possible with core modules - for example, if I'm only using Path::Class in one or two places, I might as well use File::Spec instead. Or, if this optional functionality is sufficiently large, consider splitting it out into a separate release in the same namespace.

Having said that, of course there are exceptions, for example if there are different backends that are OS-dependent. I have a module on CPAN myself with optional dependencies. My suggestion would be: Don't include the optional dependencies in TEST_REQUIRES, use META_MERGE => { prereqs => { runtime => { recommends => { ... } } } } (example). Then skip the corresponding tests if the modules aren't installed, but when you do your author tests before release, verify that the modules are installed and the tests pass. (There are of course other possible approaches, this is just one suggestion.)

* Update: Just to clarify: I mean when writing new modules, I wasn't trying to hate on modules that already have them :-) And even when writing new modules, as I said, there are exceptions. But optional dependencies add a bunch complexity, especially in testing: it really would be best to run the entire test suite once when the optional dependency isn't installed, and once when it is, and AFAIK there's no way to do that on CPAN Testers, which means you have to rely on your own local testing, on multiple platforms. And if there's more than one dependency, the number of times one should run the test suite grows quickly.