As a non-American living in Western Europe the idea of a landlord doing a "background check" on prospective tenants is terrifying. Never heard of such a thing in Europe. What the hell does "background check" even entail.
German landlords in large cities generally require a credit report (though not things like criminal record, which can be in a US background check). For large institutional landlords, you may sign a document permitting them to perform this check; the more usual case is that you request a report from the credit-report company yourself and send them a copy.
Most will minimally do a credit check. Some will check your past landlords - and won't rent to first-time renters. Some do criminal background checks, and a small portion will check personal references.
Most European countries have mandatory ID / residence registration so this is handled directly by the state rather than making landlords do it.
(Whether the UK counts as "Europe" is a subject of extreme controversy)