Therefore, if the web server were to be compromised you would need to a) figure out the key to encrypt the message; b) figure out the authentication mechanism for the message queue; and c) defeat any transaction limit / validation checking.
Well, if your web server is compromised then all this logic will be available in plain text in your PHP files, so that SQS design doesn't really change much. They probably wouldn't even need to figure all that stuff but simply to execute some of your code.
You might want an independent third party that verifies messages to increase security. That third party should have some information that is required to proceed with transaction but is unavailable to your web server, so that the web server alone couldn't prepare a valid message.
Now what that might be - it totally depends on your application. Let me give you an example assuming that you run an exchange - or any other website keeping people's deposits - and these transactions we discuss are withdrawals requested by users. This would allow for two design choices that might not be possible in a different kind of website, but are perfectly fine in an exchange: 1) each withdrawal needs to be confirmed by clicking a link sent to an user email; 2) no withdrawal is possible in 24 hours after email change.
You have these three servers: web server, verification server, bitcoind server, which are talking to each other using SQS, not knowing each another IP addresses, etc.
So user comes to your website and requests withdrawal. Your web server creates SQS message addressed to your verification server. The verification server creates a confirmation token and prepares a link to send to user email. When user receives the email, he clicks on the link and it's processed again by your web server which sends another SQS message to the verification server. The verification server confirms that the token is valid and creates SQS message for the bitcoind server to schedule the transaction.
Hacking your web server alone allows do nothing, as the verification server needs to generate a token and the token needs to be confirmed by the user. Token travels from verification server -> to the user email -> to the web server after user clicked the link -> back to verification server. And only after that round-trip, the verification server (not the web server) creates SQS message to bitcoind server. They would need to hack both web server + user email or web server + verification server to do anything. But nobody knows where your verification server is located - they don't know its IP, even your web server doesn't know the verification server IP.
Now there's one more thing to take care of to be really secure. As both web server and verification server would need access to database with user accounts, we need to make sure that hacker didn't change user email address in the users database (he will have write access to it after compromising the web server) just before sending SQS message to verify withdrawal.
So the verification server should have another database (not accessible by web server) with copy of user email addresses and it should keep track of changes in user addresses. It should sync all user addresses from the main database into its own database every hour (or more often) and detect changed addresses. Mark these changed addresses with timestamp on its own (i.e. not depending on any modified_at field in the main database as it might be faked as well). It should not allow any withdrawal for user who changed his address in the last 24 hours. Moreover, on each email change detected, it should send an email to both old and new user addresses notifying him of that change. This is a good practice anyway and by doing that from the verification server you'll make sure that user will always be notified on his email change - even if your web server was compromised and hacker changed the email manually in database (thus not triggering any email change action in your web application), the described process would trigger email notification anyway, because the verification server would detect email change and send the notification.
So now for the hacker to make unauthorized withdrawal would need: 1) hack into your web server; 2) change user email addresses in database; 3) wait for more than 24 hours; 4) in the meantime user(s) would need to ignore changed email notification message which you sent to them from your verification server; 5) only after these 24 hours after changing user emails and users not alerting you of unauthorized email change, the hacker could request a withdrawal; now verification sever sends withdrawal confirmation email to hacker-modified email address so that he can receive the email, confirm the token and the transaction would actually be scheduled. This is highly unlikely, especially when user is notified about email change (and it's done from independent, verification server, so the hacker cannot stop that).
Bonus point: in addition to the user not reacting for email change, the hacker would really need to know how this whole system works, so that he actually needs to make the email change and wait 24 hours. As the code responsible for verification will be on another server, the hacker couldn't read the code and get to know about your internal verification rules, so there's not really any way for them to know about it. Even if they know that no withdrawal are possible within 24 hours of email change, they will probably think that changing modified_at field will do the trick, not knowing that you actually track modification timestamps on a separate server and in a separate database.
Hah, that was long. Sorry I didn't draw any diagrams. I hope I's clear and I hope it helps. Of course if you're not taking about user withdrawals then this exact design might not be possible, but it should give you an idea of how that independent verifying third party might work and how to design such process.