The best route is to have a pure-Perl module that provides the interface and have an XS module that requires the pure-Perl interface and is used via the pure-Perl interface (yes, this can be done efficiently and easily). That way, if you want/need the XS implementation, then you just install that one XS module (and your install tool likely installs the interface module automatically because of the declared dependency). If somebody else has difficulty installing an XS module, then they just install the pure-Perl one and they're set as well. You don't have to try to write code to get all of the varied install tools to try to ask the user whether they want the XS piece or if they want to continue installing even though the XS part didn't build or other such complex magic.

I've seen several modules go that route though I don't recall the names of any of them at the moment.

If the XS module is wrapping some external libraries, then this whole question is probably moot. Otherwise, there are usually only a few (if any) features that can't be provided without XS (most of the time, the vast majority of the features can be done in pure-Perl and the XS is just there to increase performance and the number of bugs) or just haven't been coded yet in Perl, in which case the pure-Perl replacement likely just dies/croaks (at least for now).

But you were more asking about what you should do when things didn't go this "best" route. I'd write a wrapper module that transparently uses either the XS module or the pure-Perl module and make it require the pure-Perl module. And I'd encourage the author of the XS module to be involved and to encourage users to switch to using this interface abstraction module (which, again, usually isn't terribly difficult to write while still being very efficient, though exactly how to write it will depend on the iterface being implemented) to the point of getting the XS module to require this abstraction module.

If you can also get the author of the pure-Perl implementation involved such that the interface abstraction module is actually just made a part of the pure-Perl implementation module, then you've got the original best route that I described (but the only real advantage of this last step if reducing the number of "moving parts").

Note that it is also nice to have a hook whereby the user of the abstraction module can request that the pure-Perl implementation be used even if the XS implementation is installed. This is polite but can also be important as almost always the XS implementation will have more bugs or just not work on some less-vanilla data, etc. and will certainly be harder to tweak to work around bugs, awkward design choices, etc.

Update: Here is a block diagram of the proposal for a quick grasp of the concept without trudging through the long description:

+-------------------+
|XS implementation  |
|Either install this| ---requires--\
+-------------------+              |
                                   V
 +-------------------------------------+
 |pure-Perl module distribution        |
 |Or install this                      |
 |Other tools require this distribution|
 |  +---------------------------+      |
 |  |pure-Perl interface package|      |
 |  |Only package used in code  |      |
 |  +---------------------------+      |
 | +--------------------------------+  |
 | |pure-Perl implementation package|  |
 | +--------------------------------+  |
 +-------------------------------------+

(or)

+-------------------+
|XS implementation  |
|Either install this| ---requires--\
+-------------------+              |
                                   V
                    +--------------------------+
                    |pure-Perl interface module|
                    |Or install this           |
    /---requires--- |Only package used in code |
    |               |Other tools require this  |
    V               +--------------------------+
+-------------------------------+
|pure-Perl implementation module|
+-------------------------------+
[download]