According to Günter Nimtz, we've already measured superluminal velocities.
Many (most?) physicists disagree with Nimtz' interpretation of his experimental results, probably mostly due to the fact that tachyons potentially violate causality (remember that according to special relativity, faster-than-light means backwards in time when looked at from a different frame of reference!).
However, according to Recami, special relativity can be extended to include tachyons without violating causality (see this PDF if you can stomach the physics).
I haven't really looked into the problem in detail (I've been planning to read through this issue of Annalen der Physik for some time, but never got around to it), but my gut feeling is that tachyonic interactions might indeed be real (I hesitate to call them tachyonic particles because they'll necessarily have some pretty strange features to be consistent with special relativity).
If Recami's analysis is correct, tachyons cannot be used to do anything useful like committing the perfect murder (Bell paradox) or answering questions before they are asked when using an anti-telephone (Tolman-Regge paradox). So even if they do exist, the implications might be far from earth-shattering.
The situation might turn out similarly to the 'spooky action at a distance' due to entanglement: When first discovered, there was a lot of controversy, but in the end the physics community just shrugged, accepted that the world is a bit stranger than we formerly assumed and moved on.