Here's something that I've recently had my nose smacked with:

Every place where users can authenticate over the network to your systems should log successful authentications, including the source IP address.

Every place. No exceptions. And all of the pieces (minimally user name, remote IP, and time) should be logged explicitly in one place; you should not have to piece together this information by inference from a collection of different logs, because sooner or later you will go mad from having to do this. You should do this logging even in systems that do not directly authenticate the user but delegate it to another system and then just use the authentication result.

(For example, suppose that you have a webmail system that is actually a frontend on your IMAP server and so relies on the IMAP server for authentication and mail access. The webmail system should still log all successful authentications, partly because your IMAP server logs are likely to report the source of all of the connections as being from the webmail system instead of the user's actual remote IP address.)

It's hopefully obvious why you need this everywhere, on every service (no matter how insignificant). Partly this is because if you ever have an attacker exploiting a compromised account, you'll want to know everything the attacker did. Partly this is because you can never entirely predict what service an attacker is going to find interesting and then (ab)use. Partly this is because it's easier to make sure that something important doesn't slip through the cracks if you have a policy with no exceptions; otherwise, it's all too easy to deploy something without this logging on the grounds that you need the service now and you'll put the logging in later. (Remember, later never comes.)

Logging failed authentications for existing users is optional (my personal feelings on this are heretical, so I will skip them for now). For hopefully obvious reasons, you should omit the login name if you log failed authentications for nonexistent users.

(This is likely something that experienced large-scale sysadmins know automatically and is part of best practices and so on. Sometimes I'm slow, and it's always tempting to say 'ehh, we're too small and it doesn't really matter for this service because ...' or, for that matter, just not think about the issue when you're deploying a service. Security compromises are low-probability events for most places and most services, and security in general is an overhead.)