protobuf sounds attractive, but (unless I've missed something in protobuf's implementation), but out of the box you have 2 issues:
1. Protobuf doesn't/can't deal with fragmentation - so you'd have to ensure your protobufs are small enough to fit inside a UDP packet
2. Without a wrapper you couldn't put multiple small protobufs into a single UDP packet?
Both things are fixable by wrapping protobuf, but I suppose if you're trying to get something as small as possible, can you actually just do better by avoiding protobuf in the first place (I guess the answer is yes?)