Try shooting ahead of their movements (to the point that you "miss" slightly in front of them). This is called lead-shooting.

Imagine it this way:
Player1 shoots at Player2
Player1 sees the shot hit Player2.
Referee says that Player1 missed behind Player2's movement.
Player2 accepts what the referee said and doesn't take damage.

In this case, the referee is the server. What matters isn't what YOU see, but what the SERVER sees. I'll give some examples, but remember that the important thing you're making up for isn't distance, but time. So let's say you have .5 seconds of latency...

Something slow like a zombie walk might let you shoot directly at where you see them because they don't move too much in .5 seconds.
Something at a knight's walking speed might mean you need to shoot 1-2 tiles ahead of them because that's how far they can move in .5 seconds.
Something moving at Kat/Howlitzer/Striker boost speed might mean you'll need to shoot 3-5 tiles ahead of their movement because that's how far they can move in .5 seconds (at which point you need to just predict where they'll be and shoot into the future).

This latency thing doesn't just apply to shooting, but also things like shielding and dashing (how much earlier do you need to shield/dash in order for them to work vs projectiles?).

How do you find out how much to lead?
- One exercise I like to do is to dodge howlitzer heads/kats and try to get my shots to register as they pass me.
- If you have a friend with some patience, pick a block in Training Hall and tell them to walk across it a few times. Shoot at that block (not at the person) to try to figure out if you can make them see the shot hit them. Ask them if they see the bullet hit them after each shot, and they can tell you if you need to shoot ahead, behind, or if you're hitting them directly. What's important is that your TARGET sees your shot hit.

Depending on your latency with the server, you'll probably end up seeing that you'll need to miss in front of them to make your shots really count.

Since I already kind of have a feel for it, I just play lockdown and after my first few rounds, I get an idea of which shots I take that actually land.

It's extremely frustrating at first, I know (ex: you'll shoot a blind miss behind you and then you'll see a striker around and die long after you've walked away), but once you get the feel for your own leadshot, you'll have noticeably better hitrate.