I submitted a pull request which attempts to address this issue:

https://github.com/qos-ch/logback/pull/287

To maintain backwards compatibility it requires adding a configuration element to the SizeAndTimeBasedFNATP:

<historyAsFileCount>true</historyAsFileCount>

This changes the behavior of the SizeAndTimeBasedArchiveRemover to count all the files which exist and remove any beyond the retention count (aka maxHistory). Since the remover is only executed after a rollover this should not present a large performance penalty, but its cost will be proportional to the number of files retained (aka maxHistory). An enhancement to cache the number of files at each period in memory should be possible.