Hi Carsten,
just by chance I read this thread.
It might be a good idea to announce this somehow for package maintainers on a prominent place in the change-log of the next official release. Some Linux package systems do allow recommendation on packages.
As I understood the xdg-utils package is not mandatory for using org-mode, because it would work without xdg-open too. However, we could ask the package maintainers to make a recommendation to install xdg-util whenever, org-mode gets installed. Just a nice customer service ;)
BTW: Emacs itself does *not* require xdg-utils or refer to it as optional. That would have made it even easier to assume it is already on all Linux systems.