UDP is unreliable, as you've found out, but it does seem like the way to go. Perhaps you can simply add a step (or actually, just modify a step you already have). Basically, computer A sends out a message, computer B must reply. If A doesn't get the reply, it re-sends X number of times. If it doesn't get a response in those X times, it assumes that B is down. Set X based on how noisy your network is.

One key is to keep the UPD portion as small as possible. It doesn't sound like the packet size should be an issue, but you did mention packets fragmenting, which would suggest your packets are too verbose. There are ways to deal with packet fragmentation, but avoiding it is always going to be easier.