If said user has his profile enabled, check your private messages again. Click "reply", and you should see the profile icon in the upper right of the reply window. If no such icon is present, his/her profile is not enabled (in either case, you should see the bulb indicating online status).
Also, forum user search (at the bottom of the search page) should work as well.