Projectiles, their speed, and collisions

Argh... I've been fooling around with a projectile object and almost got it to work. I've got a projectile that flies out at an (initial) speed of 500m/s. If it hits anything in the air, it will call its OnTriggerEnter() function and if the collider's an enemy agent, it'll deal it some damage.

Alright, it sort of works. Almost because sometimes when the enemy agent is very close the trigger isn't called. That's one problem. I tried to fix that by making the collider large enough (10m at a fixed update of 50Hz), but still, since the trigger functions are called after all physics updates, the projectile will have moved considerably in that time span.

So I reduced the timestep to 100Hz, which kind of helps. Updates are more frequent and most times the enemy's collider is struck. But not all the time. Hmph.

A second problem is that since the collider is so large (and travelling so fast), if the agents are so placed: |Shooter||Victim||Wall|, the collider may actually trigger on the wall, which calls the Destroy() on the projectile without ever calling the damage dealin' function.

A final problem is that the projectile's attached mesh renders right on top of the shooter if I instantiate it as close as possible (which, because of the other two problems, I need to do).

So what are my options here?

Reduce the timestep further? (Doesn't this hog the CPU?)

Have the bullets fly slower? (Wouldn't that be less than realistic? Nevertheless, if that's how it's done, that's how it's done).

Forget this high-speed projectile poppycock and go for raycasting? (Same as above).