Clojure's Protocol - when to use it?

Coming from an OO-background I instinctively turned to protocols during my early Clojure explorations. Need to model an Aggregate? Complex internal structure, should be hidden, small set of functions operating on it? Protocol, what else?
Eventually I've learnt a bit of FP and started moving towards pure functions, feeling less and less the need to resort to the OO-ish features of the language. However recently I've been spending some time writing a Twitter-reader application and had some trouble with functions with side-effects. Long story short, I've come up with a simple rule of thumb (don't expect anything earth-shattering)

Use protocols when state is involved!

When is 'state' involved?

1. when the program maintains stateful entitites (either in DB or just in memory)
2. communicating with an external system (e.g. Twitter)

The two cases are not that different, actually. If you can abstract away from the communication details, is operating on the DB really much different from operating on Twitter? Twitter could run on your local machine on your DB after all, in theory.

So what's the benefit?

1. you can group functions together. Usually if you manage state, there are multiple operations around it. Save/Delete/Get/Update for DB, StartListeningToStream/StopListeningToStream for Twitter. Having separate methods only grouped by namespace seems somewhat off to me. Maybe a matter of taste.
2. Easier to provide new implementations. You want to replace your Mongo with Reddis, just give a new implementation. I think the cognitive load is much less if all the functions you need to change are bound together by the language itself, so you don't have to hold all those independent functions in your head.
3. Ordinary functions should be pure. If you hide your state behind a protocol, all the rest can be

An example

So the new, all-encompassing, completely universal principle you should absolutely start all your projects with, absolutely without exceptions

1. identify the moving parts in your model
2. hide them behind protocols by having a namespace for each where only the protocol itself and the factory method is public

Still a bit OO-ish? Maybe. But no-one said OO is without merits.