If you log on to myequifax.co.uk you can get a written report of your credit status sent to you within a week. It costs �3, you fill in your details online (name, dob, addresses you've lived at in the last 3 years etc) and they send you the report plus a basic guide of how to read it.
You'll be able to see if you are on the electoral register, plus details of all accounts held in your name, their payment statuses, and any credit searches done on you recently.
One last thing - when you filled in your electoral registration forms you didn't "opt out" of the public record did you? That could be the reason you're not showing up and will affect your ability to obtain credit.