We present an optical spectroscopic study of the black hole X-ray transient V4641 Sgr (=SAX J1819.3-2525) covering the 1999, 2002, and 2004 outbursts. The spectra were taken over 22 different epochs during the low-luminosity phases that follow the sharp and bright outburst peaks displayed by the system. The data reveal the frequent presence of wind-related features in H (Balmer) and He I emission lines in the form of P-Cygni profiles and strong emission lines with broad wings. The terminal velocity of the wind, as measured in the blue-shifted absorption (P-Cygni) components, is in the range of ˜ 900-1600 km s-1 , while the broad emission line wings (so-called nebular phases) imply outflow velocities of up to ˜3000 km s-1 . We show that, at least for several of the wind detections, the radio jet was active and the system was likely in the hard state. This, together with previous detections reported in the literature, shows that V4641 Sgr is the second source of this class, after V404 Cyg, where the presence of these cold wind outflows has been clearly established. We discuss the similar phenomenology observed in both systems as well as the possible nature of the outflow and its impact on the accretion process.