Após algum tempo livre e mais pesquisas, essa solução pode corrigir o problema:
find /usr/dir/logs/ -mindepth 1 -mtime +45 -delete
Parece que find e rm estavam incluindo o diretório pai e tentando removê-lo primeiro, o que explica por que ele às vezes funcionava, e então lançava erros de arquivo / diretório ausentes. O uso de -delete funcionou bem, e a adição de -mindepth 1 fez com que ele ignorasse o pai.
Para reter os subdiretórios onde eles não devem ser excluídos, adicione -type f para examinar apenas os arquivos que foram deixados. Além disso, havia uma instância em que um arquivo específico precisava ser ignorado. Isso parece funcionar para essa situação:
find /usr/dir/logs/ -mindepth 1 -type f \( ! -name "ignoreme*" \) -mtime +30 -delete