Finally found what was the root cause. There is an issue with BinaryFileManager.IsCached method. It does not account if file was unpublished.
When you call IsCached method it will get lastPublishedDate, however lastPublishedDate for unpublished binary file is DateTime.MinValue. Based on my testing IsCached method does not handle situation when ...
It seems you are right that cached Binary files are no longer automatically removed when the Binary is unpublished.
The cleanup code was removed in DXA 1.8: https://github.com/sdl/dxa-web-application-dotnet/commit/1a78d03003e614745fba9714eaf6b4c8a19066a4#diff-dc665a329e7453c1f17f6ce4e9e95524