xdg-open is installed yet also is not installed

This sounds like your package database is screwed up. First I'd identify all the versions of xdg-open that you have on your system. The type should always be used for doing this task, never rely on which or whereis.

Example

Identify all xdg-open's.

$ type -a xdg-open
xdg-open is /usr/bin/xdg-open

Find out which packages they're a part of.

$ dpkg -S /usr/bin/xdg-open
xdg-utils: /usr/bin/xdg-open

You'll want to either repeat the above dpkg -S .. for each match returned by type -a or use this dpkg -S .. search instead.

$ dpkg -S xdg-open
xdg-utils: /usr/bin/xdg-open
xdg-utils: /usr/share/man/man1/xdg-open.1.gz

I would do each, one at a time.

Reinstalling xdg-utils

If you'd like to refresh this package's installation do this:

$ sudo apt-get --reinstall xdg-utils

Thanks to @slm's tip, I tracked this down.

A while back, I followed some bad advice to make chromium-browser the default on Linux Mint. The advice was, delete usr/bin/xdg-open, then create a symlink in its place to chromium-browser.

It sure made Chromium the default browser. It made Chromium the default for lots of things.

Since then, of course, I installed the official Chrome for Linux from Google. It worked as the default automatically and I forgot about the kludge.

Unfortunately, it's hard to fix. You can remove the symlink okay, but how to retrieve the original? sudo apt-get install xdg-utils doesn't bother because it thinks it's already up-to-date. sudo apt-get remove xdg-utils is currently busy uninstalling virtually my entire system.