I also use attachMovie. In my own games, I generally give the bullet a life-span (expressed in milliseconds) and use getTimer() in the bullet's onEnterFrame handler to see if the bullet's time is up.
When the time is up, I use bullet.removeMovieClip();

With this method, the bullet is allowed to fly off the stage, but dies soon thereafter.