It is not possible to use the Import-Mailbox or Export-Mailbox cmdlets unless Outlook 2010 x64 is installed on the Exchange server against which you try to run the command.
Does anyone have Outlook installed on their Exchange box? Are you aware of any issues or problems this might present? Are there any other cmdlets that require Outlook, or any other compelling reasons to install it on your Exchange server?
I've searched for Microsoft documentation or recommendations but can't find any.
EDIT: I'm trying to export to and import from PST files, not to another target mailbox.
My suggestion would be to plan an upgrade to Exchange 2010 SP1 RU3. The SP1 removes the requirement to have outlook installed on the servers to import / export mailboxes.
Although, I do have Outlook 2010 x64 installed while trying to resolve the export to .pst issue. We have had no issues while it's been installed. We are moving to SP1 in the next week or so.
There is absolutely NO problem with installing Outlook on an Exchange 2007 or 2010 server. Exchange 2000/2003 had problems with this due to MAPI version conflicts. The newer versions of Exchange do not use MAPI for management, so you're safe. You should be aware, however, that there still exists a conflict with Outlook and BES on the same server because of BES' reliance on MAPI.
Exchange 2010 requires Outlook on the computer it is run from. It is recommended to install the Exchange Management tools on a different 64-bit computer with the 64-bit version of Outlook installed. It is still possible, however, to install Outlook on your mailbox server and run the proper cmdlets from there.
Technically, you are not supposed to install Outlook on the server. You are supposed to install the Exchange Management tools and other prerequisites on a client computer. Here is a great article that will walk you through it: http://www.msexchange.org/articles_tutorials/exchange-server-2010/management-administration/exporting-importing-mailboxes-exchange-server-2010.html