First I reccomend using a networking library (I'd use Lidgren.Network in your case)
I've heard of that before and have it open in another tab. I was going to either use Lidgren, like you suggested, or create my own library using System.NET (but that's a stupid idea considering I'm already having some trouble with this).
NEVER trust the clients, at least you have that down.
The only thing the clients should send is input data, NOT player coordinates.
Why is this? Because there's no point in 'hacking' input data.
The server sends updates. If the player gets an item or loses health, the server should be checking for this, and sending it to the client. THE CLIENT SHOULD ONLY BE RECOGNIZING INPUT AND RENDERING THE GAME. THE CLIENT SHOULD NOT BE editing player health, player items, etc and sending it to the server!
When you use Lidgren.Network, things are pretty simple, and you shouldn't get your hands dirty. I believe you said you're using XNA, and Lidgren supports it.
One final thing is verification of syncronization. Most people implement interpolation of sprites, but an easier way for you to start out is to send the actual player coordinates from the server to the clients each 2-5 seconds to verify that everything is synced.
This way the client doesn't wait for a server update for the movement of sprites, but it uses both client and server data to guestimate where the sprite should be.
Ok. I think I get this enough to have at it. Time to give Lidgren's tutorials a spin. I'll assume that the delay between packet sendouts is dependent on the game and would require some tinkering, as well as dependent on levels of latency.
Some games compromise on this and allow clients to determine player positions and run physics themselves, while the server just does some basic sanity checks and boots players that are detected doing something naughty by moving their coordinates too far too fast. This has the advantage of responsiveness and less reliance on low latency/high bandwidth connections, but the drawbacks of potentially allowing players to cheat their position if they do something illegal by the game logic but that doesn't get caught by the server's naughtiness filter, or the server's naughtiness filter catching something legitimate. Whether it's the right approach for you or not depends on which things you'd rather sacrifice. Real-time networking involves a lot of tradeoffs...latency is an unavoidable problem that throws a wrench into pretty much everything you do.
Given that the game will have some precision movement around slower-moving bullets, I'll have to sacrifice some latency for control over player position. The trick will be finding the fastest way to send the server input. If I allow gamepad input, I might do a "slowX" and "slowY" bool value to determine that the player is moving slowly in a direction... It's still a sacrifice in precision, but it's better than nothing. Yet again, I may do the server-side sanity-check like you suggested if I deem the risk worth the latency. Only time will tell.
Thank you all, it seems like this case is solved.