Picasso кеширует изображение на уровне http. Проверяйте заголовки которые отдаёт сервер хостящий картинки (ключевые слова "Cache-Control", "public, max-age, max-stale")
Если сервер отдает с малым временем "жизни", то теоретически можно унаследовав стандартный http клиент picasso подсунуть нужный заголовок - но это тяжко. Вообще на стеке сам автор на это отвечал - поищите
Также необходимо проверить размер дискового кеша и кеша в оперативке для picasso. Но ваша проблема скорее всего не в этом