Server Iframe integration produces - MD5 did not match error while on test mode

We were trying to test out Iframe integration payment method, but for some reason it did not work. Every time we got re-directed back to payment review page.

Checking the logs on SagePay shows us this message - Transaction completed but Vendor systems returned INVALID or ERROR in response to notification POST. Transaction CANCELLED by the Vendor..

After few unsuccessful attempts I added a line in "commerce_sagepay_server.inc" to push out on watchdog log what's happening there. My code looks like this

watchdog('test_error', 'Order message %message for order %order_id', array('%message' => $notification['message'], '%order_id' => $order_id), WATCHDOG_NOTICE);

I put it around line 422.

Finally with this small hack I managed to get the contents of $notification['message'], which were - "MD5 did not match - signs of tampering" (see screenshot attached).
Contacted SagePay, they responded that this is our side to make sure that both $_REQUEST["VPSSignature"] and concatenated md5 hash of message contents should match.

Is there any idea why these two do not match?

FYI - We were using SagePay test server.