Is there a difference? Both versions are common.
If there is a difference, which do I use when, and why?
Grammatically they are interchangeable. The very definition of "unavailable" is "not available". However, my gut tells me something else. When I see 'unavailable' it immediately connotes that it's a temporary condition:
Whereas when I see 'not available' it implies to me that it's a stronger or more permanent situation. Maybe because of the emphasized not?
While you could legitimately substitute "not available" for "unavailable" in those examples (and vice-versa), I wouldn't.
Both are perfectly valid, but I would take issue with the implications of OP's "Both versions are common" - relatively speaking, they're not...
In short, unavailable is the standard form. But noting OP's comment regarding negation vs. not, I suggest that, for example...
...is normally preferred over...
Both OP's versions mean exactly the same, but as @Lynn says, the reason "un-" is more common is because it's temporary. With something more "permanent", like my example above, or the more extreme "Not available at any price", the "un-" version is actually significantly less common.
They both mean the same, they are just different constructions.
Temporarily unavailable seems "lighter", as it contains only 2 words, whereas temporarily not available contains 3, which are redundant, as unavailable is a grammatical word which bears all the required meaning.
Use less words, be easier and faster to understand.