Any reason NOT to slap the 'synchronized' keyword everywhere?

You shouldn't, and you probably need to reconsider your design. From my experience, synchronization at this level is just not scalable. It might fix your immediate problems, but won't help to fix your overall application integrity.

For example: Even if you do have a "synchronized" collection, one thread may want to call two "synchronized" methods in one go, but don't want another thread to see the intermediate result. So any caller of a fine grained "synchronized" API must be itself aware of that, which heavily degrades the (programmer-) usability of this API.

For a start, it is best to use worker threads. Isolate specific long running tasks so that separate threads take one block of immutable input and - when finished - enqueue the result in the main thread's message queue (this of course should be synchronized). The main thread may poll or explicily wait for a signal if it has nothing else to do. The specific details depend on your performance requirements and application design.

On the long run, try to understand implementations of the ACID transaction model of database implementations or message passing concurrency, ... for example, the Erlang language will give you a lot of inspiration. These are synchronization models that are proven to be scalable. Take the best of them and try to apply these concepts to the multithreaded application you work at.