If you open a new PM and slowly start typing the user's name, a list of suggestions will pop up immediately below where you're typing, so you can choose the right one from the list.
If you want to find a profile anyway, there are a couple of ways. You can use the advanced search and type the username in the relevant box - again slowly to give the list a chance to pop up. Then click search and you should come up with a bunch of threads that the user has started. If there aren't any, then try ticking some of the boxes and search again until you get a result. Then you can open the thread and click directly on the username and choose to go to their profile. Alternatively, if you're 100% certain how to spell the username, then simply go to your own profile, double click your name in the address bar of the browser to highlight just the name, then overtype the username with the one you're looking for. If their username is two words, then you have to add a dash to take the place of the space, ie john-doe. Press enter and the webpage should change to the other person's profile.