Long time ago I tried to open a bank account in the UK as I was moving to there. Main problem was proof of address, I couldn't proof it because I didn't receive

Long time ago I tried to open a bank account in the UK as I was moving to there. Main problem was proof of address, I couldn't proof it because I didn't receive the utility bills and/or contract as my employer was paying it. Even having money outside UK didn't count at the end my employer had to write a letter to proof I had a job, and lived at address X and then I got a shitty bank account were I could only use the bank's ATMs. Luckily a half year later I could upgrade to a normal account once I was able to get a mobile phone plan (similar proof of address issue)