I took the road to Bayjin and Madras didn't want to go, so I released him, thinking I'd find him again back where I found him. Alas, he was not there. Does he go there or somewhere else?

He should be back home. If I remember correctly, RFS-81 is the only NPC who stays where you leave him.

I thought so as well, but I went to Trynton and he wasn't there.

Perhaps he got waylaid by rapax. Try looking for him in the kitchen of rapax castle. :D

Madras should go back to his observatory in Trynton. Are you positive you're checking in the right place in Trynton?

Also: I noticed that sometimes when you dismiss an RPC they'll show up next to the party, and not leave for home until you leave the area. Is it possible he was attacked and died before he had a chance to go back home?