what type of scripts can you run on your server?
if you want to, I set up private messaging on my forums in PHP and can tell you how if you wish.
first, depending on what database system you run, you'd need a table with data like:
sender, receiver, subject, time, message, read?, etc.
... get back to me if you run PHP and I can help you more then if you want.