"The free version mentions capability to update contacts in the "Public folders". I am not quite familiar with exchange, so I would like to know whether the free version can upload/update company wide contacts (ie first name, last name, email address, etc...), or is it just your personal contacts that can be created/updated?"

You can use this tool to update a PST, but that was really included for developer testing purposes. You would want to use this with an Exchange Server -hence the name xp_sql2exchange!

Re: geniusconnect; yes, that is good. But I am not enthusiastic about relying on a single instance Outlook app to push data. It's very good for occasional pushes...