How can you move a document with its version history to a new library?

Tools:

 Lars Fastrup has created a tool that does just what you want: CopyMove for SharePoint

It also has a web service API.

2 document libraries

Both contain multiple documents

The documents have multiple versions

using objects like SPExport and SPImport

the copy, move actions of the content site and structure (sitemanagement.aspx) are performed using this API.

Current Limitations:

Document libraries should be in the same site.
Only default document library view is supported:
All views should have title.
All views should have summary toolbar.
All views should have the type and the name columns.
Only files with title can be moved.
You can’t drag folders or drop into folders.
Current Features:

Copy Operation has been added.
Folders are supported now.
Planned Features:

Delete Document by drag it to Recycle Bin.

Support Multiple Item Selection.