I managed to get it installed. I'm not sure if it was the best way to do it, but so far it works. I haven't tested zarafa-licensed yet as I don't use Outlook myself. The problem seemed to be that the zarafa package tries to install the same file as installed by the zarafa-licensed package. I was able to fix it by forcing the package to be installed:
sudo dpkg -i --force-all /var/cache/apt/archives/zarafa_6.40.8-27223-0lucid1_amd64.deb
sudo apt-get dist-upgrade
The install and upgrade completes, but I also had to restart Apache for Zarafa to work:
sudo service apache2 restart
Will try Outlook later.