I've just managed to get this to work after spending two days taking it apart. For me this was down to a clash with SEO URLs - which creates the ampersand issue I've seen mentioned a lot. I've created a working file and uploaded it here in case it's of any use: http://addons.oscommerce.com/info/8292
I tried the new Addon at http://addons.oscommerce.com/info/8292 using the new sage_pay_server.php file, but still experience the same issue, with the 5006 error code.
Being honest, I am currently waiting on client to finalise setting up of new account with a different payment processor.
I receive this error, using both 2.2 and a clean install of 2.3.1, and also with SEO URL's turned off in 2.2. It could be a setting on my server, or something else. but this has me beat!
Additionally, this type of error can be caused by a corrupt protx_direct table in mysql. If none of the above work, or you get problems just after a server reboot or load issue, try repairing your OSCommerce tables in mysql.