Over the years I've swayed backwards and forwards between promoting logging everything at the appropriate levels (trace, info, etc...) and thinking that any is a complete waste of time. In reality it depends on what is going to be useful to track down or required (logging can be a cheap way of maintaining an audit trail).
Personally, I tend to log entry/exit at a component or service level and then log significant points in the processing such as a business logic decision or a call on another service/component. Of course errors are always logged, but once only and at the place they were handled (the stack trace and exception message should have sufficient info to diagnose the problem) and any service/component interface should always handle an errors (even if it is just converting it into another more appropriate to the caller).
The problem with logging stuff on the off chance something goes wrong is that you end up with too much information that it is impossible to identify the issue, especially if it is running under a server as you end up with loads of intertwined log entries. Obviously you can get around that by incorporating a request id in the entry and using some software to filter on that. Of course you also have the case where your application is distributed and/or cluster and you have multiple logs.
Nowadays I would never actually write trace entering/exiting entries code, the code just gets in the way and it is so much easier to use something like aspectj if it is really needed. Using aspectj also would guarantee to be consistent (you can change the log format in one place rather than having to change every operation) and accurate (in case some refactoring adds a new paramater and teh developer forgets to add it to the logging).
One thing I have thought about doing or looking to see if someone already has is a logger that will hold the entries in memory, then if an error is encountered they are written, if the operation succeeds the entries are just discarded. If anyone knows of one (ideally for log4j) please let me know, alternatively I have a few ideas on how to implement this if anyone is interested in doing one.