How can I generate reasonably short temporary unlock codes? I need a way to generate temporary unlock codes for an application to use when it can't go online to confirm that its activation subscription is still current.

The application needs to able go offline for 30 days without needing to re-authorize, and this would just be a fallback option for an extended network outage/etc.

My first thought was to just store a timestamp for how long to remain unlocked combined with an RSA signature that the application could use to confirm the unlock came from us and wasn't something the user just made up.  

This appears to meet our security needs if we embed the public key in the application (if a cracker modified the binary they could just remove the check entirely instead of installing their own key).  For normal operation sending the data down as part of normal data transfers to/from the associated web application means that we could do this without any particular difficulty.

The problem I see is that since this needs to be usable if there's a network outage the unlock code needs to be short enough to send over a phone call or the equivalent.  An RSA signature with a secure key length fails there.
Use hash based cryptography.
First, define a one way function F. It takes as input a small (10-16 byte) string and uses a secure hash function (EG:SHA2) to produce another string of the same size.
We number each day from (Jan 1 2000) to (Jan 1 2100) with a number n (n=0 ... 36500)
Each day is assigned a code. If the user has the code for a particular day, they are allowed to use the software for all days leading up to and including that day. If we supply the code for day x we don't care if the user can find the code for day x-1 since the code for day x allows them to use the software on that day too. With that in mind, we do the following:
code(x)=f(code(x+1))
The codes form a chain. For each installation, you pick a random code for day 36500 then hash it repeatedly until you get the code for day 0. You then sign a message telling the application the day 0 code.
At that point, give out the code for a particular day to unlock the software up to that date.
Anyone can apply F to a code to get the code for the previous day. But they can't reverse F to get the code for the next day. Since you picked the code at the beginning of the chain you have all of them. This is the asymmetry that makes this system secure. Yes, asymetry ... this is public key cryptography.
To verify a code, the application applies F repeatedly until it reaches the day 0 code. If this does not happen within whatever the set length of the chain, the code isn't valid. Keep a counter during this process to get the code number. Enforcing this limit is not necessary for security it just times out the verification process if the user makes a mistake when entering the code.
Implementation
F can be truncated SHA2. The number of bits kept determines the security level. 80 bits is plenty.
You'd need a binary to text encoding to make this something humans can read and enter into your application.
My current machine can do ~1e6 SHA2 ops per second. That's 3000 years worth of unlock codes. Traversing the chain for generating codes on the server and verifying them on the client won't take much time.
Trusting the Clock
This relies on the application having access to the right time. Users can always change the system time so that's not something a license enforcement system can fix. If the application does something time sensitive (Like recording timestamped records) users might not want to run the software with the wrong time. I'd recommend keeping an internal saved time value which increases while the software is in use and can never run backwards. That's the best you can do. The user is always free to make a system image and restore from backup as many times as they like.
Some things you should already be doing.
I'm assuming you already have a per install ID saved somewhere. That's kind of a requirement for this. Each installed copy of the software has to have a unique ID, a code(0), and a stored signature of the (ID,code(0)) pair for this to work. This prevents the client from deploying lots of identical images of the same installation and using the same code for all of them. This is another thing that can't really be helped.
If you give the client software that gets installed on a machine and will run, the client can make a full system backup. As I mentioned before, they can restore from backup and turn back the clock as many times as they want. But they can also re-image another machine from that same backup. Handling both of these cases is a cat and mouse game of them trying to spoof the environment your application runs in and you trying to make sure they're not doing that.
Deriving an ID from hardware Is one simple option. This prevents the same license data from working on another machine ... but IDs can be spoofed. In this cat and mouse game you try to get legitimate unspoofed HW ids and the client tries to feed your application spoofed values. There isn't anything that can be done about this short of special hardware like TPMs.