Myth Busters just did a segment on this -- if fired straight into the air they don't come down and kill.
Yes, they do. Oh, so maybe not straight up, but they do come down and kill. That's a fact.
That bullet fired straight up eventually comes to a stop, and then falls out of the sky, just like that pebble. It's fairly dense (made of lead or such), and fairly compact, so would have a nasty terminal velocity, more than most pebbles. But nothing like its muzzle velocity.