In addition to what Roger said, there are quite a few different factors when it comes to perceived velocity. Often times you will hear about guys like Trevor Hoffman and Johan Santana having a fastball that's "sneaky fast" and that's because even the best batters don't know what's coming (pitch-wise). If they wait back on the off-speed stuff the fastball's gonna pass right by them before they can react (even though Johan doesn't typically get over 93 mph, he's still considered one of the best pitchers, if not the best, right now. And though Hoffman doesn't blow his FB by anyone, he is able to shut down batters w/ his change-up). All this to say: your other pitches can attribute to how effective your fastball is.
Another part of "perception" is in the delivery. Dontrolle Willis never had the best stuff, but it was really hard to pick him up behind that high leg kick. I faced a similar pitcher this last fall- didn't throw over 75 I'll bet, and he looked like meat from the on-deck circle, but his motion was so distracting from the batter's box that he was able to throw you off just enough to get outs.