You have to be doing something wrong. The only way you should be losing packets is 1) An unreliable network 2) You are sending data too fast to be handled by your receiving program. 3) You are sending messages that are bigger than the UDP max message size 4) Each device in your network has a max message size (MTU), so you might be exceeding a limit there.
In case #1, since you are sending on the same machine, the network is not even involved so it should be 100% reliable. You didn't say you had 2 network cards so I don't think this is an issue.
In case #2, you usually have to send a heck of a lot of data before you start dropping data. From your description, that does not sound like the case.
In case #3, make sure all your messages fall below this limit.
In case #4, I'm pretty certain if you meet the UDP max message size then you should be ok, but there very well could be some older hardware or custom device with a small MTU that your data is going through. If that is the case then those packets will be silently dropped.
I have used UDP on many applications and it has proven very reliable. Are you using MFC for receiving the messages? If you are, then you need to read the documentation very carefully as they clearly state some issues that you need to be aware of, but most people just gloss over them. I've had to fix quite a few of those gloss overs when people couldn't figure out why there messaging isn't working.
EDIT: You say that your packets are implicitly reordered. I might begin by verifying that your implicit reordering is really working correctly. That seems like the most likely candidate for your problem.
EDIT#2: Have you tried using a network monitor. Microsoft has (or at least used to) a free program called Network Monitor that will probably help.