That is really odd, I thought Messenger was built-in to all WM5 devices. Windows Live Mobile is out on beta and works great (way better than the built-in version). You can download the
Windows Live Mobile CAB file here (copy it to your device or storage card, run, and you're good to go).
I'm not sure if you can just unzip this and put it in your Windows folder and it will work, but I've attached the MSN Messenger program file that comes built-in with Windows Mobile 5 if you choose not to go the Windows Live route.