I think it would be a good idea to manage contacts as a FiFO stack based on advertisement time.
When you hit the limit new ones would be added with some form of filter applied (user/repeater/room/hops) but the oldest where you have not not seen an advertisement is dropped. This would naturally remove stale contacts and repeaters over time.
Favourites could be fixed to never get removed and contacts could be favoured over repeaters somehow if that was beneficial.