Hi Kurt, We had an IRC conversation on this topic with jcristau this morning, and he explained that he thinks the Recommends is enough or even too much already because Xvfb is a significant amount of functionality provided by the xvfb package.
My personal opinion is that a lot of use cases for depending on xvfb are build-deps, but I was told during that conversation that Xvfb can be used in embedded environments where the deps should be as small as possible. While thinking at the root of the problem (the build-deps did not follow a recommends), I wonder whether you'll let APT honor recommends when it does so by default, or whether you'll configure it specially not to so? Bye, -- Loïc Minier