Birmingham used the citys name and villa didnt. Villa are by far the bigger club and bigger name in football. Nothing to do with badges, Icons or naming rights...it's success that produces recognition. We have had none for decades. We have to become a more succesful club to earn that....a bird on a crest (at this moment in time) would be moot.
Few could tell where Villa are located though. Not having the city name (in a two team city) definitely contributes to being overshadowed. Say Liverpool to a continental European (or pretty much anywhere outside UK/Ireland) and they will only think of one club. It hasn't harmed the London clubs because A.there are many teams, B.there isn't a team called London to instantly identity with. Also I've seen London added to team names in Europe, ie. Chelsea London, Arsenal London.
Real Madrid, Atletico Madrid, Barcelona, Valencia, AC Milan, Inter Milan, Roma, Ajax Amsterdam, PSV Eindhoven, Glasgow Celtic, Glasgow Rangers, Manchester United, Manchester City, Liverpool, Bayern Munich, Paris St Germain, Marseille, Monaco etc. etc. Teams that are instantly identifiable with a place. Juventus are the only team in Europe that I can think of that aren't affected by having another team with the city name.