I don't think overdressing could ever be a factor for deciding who to offer a position to. Underdressing could, as it gives the (perhaps wrong) impression that you are not too serious about the job.
About your last comment I feel I need to point out that "Europeans" are a bunch of different guys from different countries, languages and cultures. I work in industry and to give you an example in my department we wear jeans (we are in discovery), the in vivo people dress up a bit more and the translational guys look like business people (with exceptions). And this is within the same division of the same company in the same country. I would still expect people to dress up a bit for interviews, though.
In the academic labs that I've seen there is also a mix, with some PIs dressing business-like and some quite informal. Even in academia in most cases people "dressed for interviews", as you describe. Was it a faculty-type position or a postdoc one? I could see many postdocs no bothering to shave.
Now the strange part is what you say about inviting all candidates to give talks. That is something I had never seen!