We were having some trouble getting our Paypal Payments Express implemented in a Magento site (1.1.6) and we kept getting the same error:

This transaction is invalid. Please return to the recipient's website
to complete your transaction using their regular checkout flow.

We combed through forums and wikis and, much to our great consternation, nothing was working.  Finally, after what seemed like hours, we found the answer;  it was the PayPal link.  We had semicolons in it where there are supposed to be none.

Here is the link that worked for us:

https://www.paypal.com/au/cgi-bin/webscr?cmd=_express-checkout&commit=&t...

Now everything is peachy.