I'm also from a non-EU country, so this rule applies to me. I've been living and working in Germany for a few years, and while this rule does exist, I've never seen it used to deny me a work visa.

> I think the company also had to agree to allow employment agency to, either anonymously or publicly, publish ad for the job themselves for a couple of weeks.

Yes, the company has to prove that they at least tried to hire Germans or other Europeans. However, just because there are potentially people who are qualified, doesn't mean the company is obligated to hire them.

The company is obligated to show that they published the job description and allowed Europeans to apply, and that they made some amount of effort (e.g. interviews) for Europeans, but none of them had the skills, or fit the team, or were willing to be paid the salary offered.

> Note: There are different types of visas, and this might not be a requirement for all of them, but it was the requirement for me.

Typically you can avoid this if you have studied a Bachelor or Master degree in Germany, as then you are viewed as a preferred candidate and are basically on the same level as native Germans (some restrictions apply).

We've actually been trying to hire another team member at my current company, and of all the applications we received, less than 10% of people were German, and probably only 60% were part of the Eurozone. This isn't a job which requires rocket science, but seemingly no Germans want to apply, so we're going through the process to get a visa for someone from a European (but non EU) country because they were the best candidate and didn't have ridiculous salary expectations (someone said they wanted 120k EUR for a mid-level IT position... mmmmmmkay, no)