Eu passei bastante tempo investigando esse mesmo problema e cheguei à conclusão de que o "Fornece" é ignorado porque o xen-utils-4.0 tem um "Depends" com versão no xen-utils-common.
Citando o Manual de Normas Debian :
A Provides field may not contain version numbers, and the version number of the concrete package which provides a particular virtual package will not be considered when considering a dependency on or conflict with the virtual package name.
Se os Dependentes não fossem versionados, as provisões seriam satisfeitas, no entanto, um Provides, que é sempre sem versão, nunca pode satisfazer um Depends com versão.
Infelizmente, eu não tenho uma solução além do que você já propôs: manter o mesmo nome de pacote e ter um número de versão maior.