There is no time delay, both are happening at the same time.
There problem is that you are doing the change on max-height, and besides that, to a huge value.
So, the transition when it is growing is very fast (because the pixels / second are high), but instant.
The shrinking transition begins inmediatly, but is invisible in the 500px - 16px interval (or to whatever is your real height), then happens fast, but (aparently) delayed.
You can:
a) transition the height and not the max-heght
b) set a max-height more close to the higher height that you expect
The a posibility has the problem that you lose flexibility. Your li's can no longer have the height that is calculated from their properties, but the one that you fix. This, however, can be done somewhat better using ems, like height: 1.2em; or so.
And, about what is happening with the max-height transition. Lets say that the hover state is set to max-height: 100px; The height is 18.9 px in my browser. (and you don't expect that to be modified by max-height.
Now, let's say that you are going to max-height: 0px in 1 second. The transition is calculated based on these values (and nothing else!). This gives that at 0.5 s, half the transition has gone thru, and max-height is 50px. The height is naturally still 18.9 px.
When 0.7 s have gone thru, the max-height is 30px, and the height is stll 18.9 px.
There is no feedback from the height to the max-height that can be used to modify somehow the initial and final values of max-height.