In this situation I would advise you to invest time into figuring out your data set and make a custom solution. My reasoning is as follows.
Should you choose something that is off-the-shelf you will be running good, stable code that is maintained by someone else and you will feel good about code reuse and will make the deadline. But if this code is not suited to your particular needs (unless you are really lucky) you will not be saving yourself as much as you could with a custom solution. Especially because it seems that you already can see a way to save yourself from sending redundant information (i.e. the year in a date time stamp).
Once you have an idea of what you want to send and remove all the information that the receiver can guess or infer from your messages then you can apply compression. And I would recommend a compression method that I have been looking at for a couple months now, Arithmetic Coding. You can find an implementation by Michael Dipperstein here but it may need a little work to plug it into your solution. A really good description of the algorithm can be found here in this pdf.
The reason I'm giving you that link instead of some C# code is that I suspect that since you mentioned a satellite link that you are dealing with an embedded system and that you are probably coding in C or C++.
Do note that my recommendation of Arithmetic Coding means that I'm recommending that you do a lot of work here.
However, my assumption is that you really need to make this efficient. With compression the efficiency comes from understanding your data-set and customizing your algorithm for it. If you're ok with a slightly less efficient approach then there are more genric algorithms out there...