After migrating a Magento store to a new server, an exception stating "Wrong Order Id" followed by the Order Id was showing up in the logs.  The store is using Paypal Website Payments Pro and Magento is version 1.4.1.1. 

I found the lines of code in app/code/core/Mage/Paypal/Model/Ipn.php that generate the error being logged:

    protected function _getOrder()
    {
        if (empty($this->_order)) {
            // get proper order
            $id = $this->_request['invoice'];
            $this->_order = Mage::getModel('sales/order')->loadByIncrementId($id);
            if (!$this->_order->getId()) {
                throw new Exception(sprintf('Wrong order ID: "%s".', $id));
            }
    ...

This code appears to first try and look up the order id by getting the invoice number.  In the case of my store, the invoice number and order number are not the same.  On this hunch however, I reset the invoice number to be in sync with the order number.  This was done by editing the eav_entity_store table, which stores the last id number for the orders and invoices.  I raised the increment_last_id value for the invoice (entity_type 16) to be the same as that for the order (entity_type 11).  Note that the entity types are defined in the eav_entity_type table.  Look there if you are not sure which row to change.

After this change, I placed an order and presto... no more "Wrong Order ID" errors!

Update:

I spoke to soon.  Each time I apply this fix the error does not appear for a while.  But it always pops back up again, I presume as soon as the Order Id and Invoice Id get out of sync.  The error is logged, but does not seem to be causing any other problems, so for now I'm planning to leave it be. I'll post again if I find out more!