We report on the search for very-high-energy gamma-ray emission from the regions around three nearby supersonic pulsars (PSR B0355+54, PSR J0357+3205 and PSR J1740+1000) that exhibit long X-ray tails. To date there is no clear detection of TeV emission from any pulsar tail that is prominent in X-ray or radio. We provide upper limits on the TeV flux, and luminosity, and also compare these limits with other pulsar wind nebulae detected in X-rays and the tail emission model predictions. We find that at least one of the three tails is likely to be detected in observations that are a factor of 2-3 more sensitive. The analysis presented here also has implications for deriving the properties of pulsar tails, for those pulsars whose tails could be detected in TeV.