It fits well into package qubes-whonix-workstation-packages-recommended.

https://github.com/Whonix/qubes-whonix/blob/master/debian/control#L69

So I'll add to Depends:...?

pulseaudio-qubes | qubes-gui-agent,

The first part pulseaudio-qubes is for Qubes R4 support and the latter part | qubes-gui-agent is for Qubes R3.2 compatibly.

Does that look alright to you? @marmarek

Will that really works for 4.0? There is also qubes-gui-agent package, so it isn't clear to me that pulseaudio-qubes will really be installed. Perhaps pulseaudio-qubes | qubes-gui-agent (<< 4.0.0)?

True, my suggested solution might work for new builds but might not work
for R3.2 -> R4 upgrades.

Perhaps pulseaudio-qubes | qubes-gui-agent (<< 4.0.0)?

That wouldn't work for Qubes R3.2, since there is neither
qubes-gui-agent (<< 4.0.0) (highest available version is
3.2.18-1+deb9u1) nor pulseaudio-qubes.

Do you see any solution?

(highest available version is 3.2.18-1+deb9u1)

Exactly, this do meet qubes-gui-agent (<< 4.0.0) criteria - version is lower than 4.0.0.
Not sure how to force installing pulseaudio-qubes on 3.2->4.0 upgrade (instead of keeping old qubes-gui-agent).

In T641#14707, @marmarek wrote:

Not sure how to force installing pulseaudio-qubes on 3.2->4.0 upgrade (instead of keeping old qubes-gui-agent).

It's a manual, documented process anyhow. Can be listed here:

https://www.whonix.org/wiki/Upgrading_Whonix_13_to_Whonix_14

@Patrick
Installation of pulseaudio-qubes is now included in the 13-14 upgrade guide under Qubes-Whonix instructions.

The current Whonix-14 templates from Qubes unstable correctly have no vlc in whonix-ws, although vlc libraries, vlc-data and vlc-plugins are still included.
Whonix-ws has the vlc binaries and browser-plugins, as expected.

I think that's enough to close this, unless all traces of vlc should be purged from the gw? If it was necessary to remove the vlc backend, it would be possible to replace it with phonon4qt5-backend-null