I released him from his prison but I couldn't recruit him, so I let him go his merry way. Fallout.wikia says his location is the Prison Building on black mountain, I returned there but no Raul.

Is there some other location where I'd find him or is this another NPC disappearance bug?

Have you looked to see if he's at http://fallout.wikia.com/wiki/Raul%27s_Shack?

After you release from Black Mountain, he tells you that he'll be at his shack if you decide you do want him to follow you. He even marks it on your map. It's just East of the Gun Runners basically. You'll know it cause there will be a small Brahmin calf walking around the front of his shack.

He's at some place called "Raul's Shack". Wonder why it's called that.

I haven't found it Raul's shack yet. I'll start searching because he's probably over there.

Thanks for your help.