Agreed, in this case floats are vital. You do not want to use integers when moving at non-integer values, if your not moving in solid integer numbers then you need floats to actually remember the position, instead of rounding off the position each time. If you use floats, then a bullet will fly straight to the destination and hit it perfectly, like in jfroco's example - without floats the bullet would probably just be restricted to 8 directional movement, diagonal or straight - no inbetween.
One thing though, with bullet movement, you have to consider collision first and foremost. If you are using pixel based collision for example, you might only want each bullet to move 1 pixel at a time (as a float though), so the movement would be a standard -1.0 to 1.0 vector, and if the speed is 5, then that means moving 5 times instead of moving in a chunk of 5. This would prevent any collision pitfalls, like if the bullet passes right through thin obstacles.
In 3D, the movement needn't be a vector so much, it could move a bullet 50 units, but with line intersect collision that's fine, because the whole path of the bullet would be checked.