By combining Herschel-SPIRE observations obtained as part of the Herschel Virgo Cluster Survey with 21 cm Hi data from the literature, we investigate the role of the cluster environment on the dust content of Virgo spiral galaxies. We show for the first time that the extent of the dust disk is significantly reduced in Hi-deficient galaxies, following remarkably well the observed "truncation" of the Hi disk. The ratio of the submillimetre-to-optical diameter correlates with the Hi-deficiency, suggesting that the cluster environment is able to strip dust as well as gas. These results provide important insights not only into the evolution of cluster galaxies but also into the metal enrichment of the intra-cluster medium.