In the end, just fixing the compatibility issues as people report them is actually the easiest way to handle the dependency mess, I think. Most issues can actually be fixed pretty easily, and the few tricky cases don't take that much time either, relatively speaking, since libraries typically release only a couple of times per year.
Bundling the correct versions of the dependencies would probably work most of the time, but it's really messy and could still break when distros update their compilers or the libraries that you didn't bundle. Distros that want to package your game will also remove the bundled dependencies and use their own libraries instead, so you'll have to fix the compatibility issues anyway if you want to be packaged by them.
Telling users to install specific versions of libraries just doesn't work since it'll make compiling unbearably difficult. I'd imagine that most people would give up straight away if the dependencies can't be installed with the package manager, and the remaining users will require so much support that it would have been faster to just work around the issues in your code. The distro packaging issues will also apply in addition.
It's a pain, but relatively minor compared to the alternative of other people not being able to compile the game at all.