For some reason, pidgin sometimes refuses adding gmail-XMPP-contacts with the above-mentioned error-message, which translates to “service-unavailable”, if you enter a local alias when adding the contact. Removing the contact and re-adding it without entering a local alias will solve the problem.
Thanks to leowandersleb.de for the useful hint.
