Huh. Don't know what could have been causing that problem. I've looked through your plugin and there's nothing that should be causing the problem you're describing.
I do agree that your plugin should not ship with Relink, but I figured you would keep the configuration file included with your project. If you have the tiddler...
included, with the text content of "title", then you don't have to do anything else. And (in theory) anyone can install your plugin and/or Relink in any order they choose. It's up to them, and your plugin would work fine without it. I'd push this change to show you what I mean, but I can't find any sort of git repository.
Basically, the files listed under your plugin's contents would be:
Which looks a little weird, but is entirely legal, and how a lot of cross-plugin integration is done. That config file is the only interaction you'd have with Relink. It does nothing if Relink isn't around, but if they ever get around to installing relink, then it will automatically come to life and integrate with the relinking whitelist. (If it doesn't, that's my problem.)