The xdg-* scripts run update-desktop-database and update-mime-database after installing files, so it should depend on the package providing those.
fixed
Reopening, since this has created a circular dependency: xdg-utils -> desktop-file-utils -> emacs -> gtk+ -> cups -> xdg-utils Not sure where to break this, maybe xdg-utils could be moved to PDEPEND of cups? Adding printing team to CC.
Moved desktop-file-utils to PDEPEND of xdg-utils, as discussed with drac.