str_replace performance in large mailing script

Hi all, I have a mailing script that sends individualised mails to users(some users even get more than one mail). I have a template html mail file. I individualise this by using str_replace function. It is really slow. Can anyone point me to some performance tips? I was thinking of including an modified template(with variables) in my message part. Thanks for any help! Fred