How do I make an object always face my camera in the Game Engine?
Use a simple cube (or rectangle, or whatever shape bullet you want) for the physical bullet. Parent a plane to your bullet's physics object. Set the bullet to invisible, and the plane's physics type to no-collision.

To make the plane track the camera, you can use the method you mentioned of edit object > track to. However, there is an easier way. You can set a material so that it will always face the camera. On your no collision plane, add a material. You can add your bullet texture, but the only setting that matters to make it track the camera is under the material's "game settings." Select the drop down for "face orientation" and select "halo" instead of "normal." What does this do? I'm glad you asked! If, for example, you were using a picture of a tree, you could use "billboard" to make the tree track the camera with rotation only along the Z. However, "halo" tracks the camera on the X, Y, and Z. You may need to go into edit mode in your plane, and rotate it so that the plane is facing it's X axis, for the face orientation setting to work.

Here is the entire process: