Names and Deed Polls
There is no concept of a "legal name" in the UK. The name you go by is your name. It is perfectly legal to go by two names as long as you're not doing it for fraudulent reasons. For example, someone who changes their name after they get married might continue to use their old surname for work and their new one for everything else.
I wrote a blog post about my experience with changing my name: Changing Your name by Deed Poll.
You do not need to pay for a deed poll. There are companies who charge a small amount to print one for you but they try and claim these are more "legit" than one you print yourself.
Enrolled vs Unenrolled #
Unenrolled is just that: you've made the deed poll yourself either through one of the free services, or simply written one out on a peice of paper. I printed mine (do multiple copies, you'll need it) on some certificate paper, but you don't actually need to do that.
There are very limited circumstances where you need to get your deed poll "enrolled". That is, your new name will get put on "public record" and it costs ~£40.
Some companies will claim they need an enrolled deed poll to change your name on their system: this is false. They have an obligation to keep your information up to date and an unenrolled deed poll is just as legal as an unenrolled one. If this happens, escalate to higher management. They'll back down eventually.