That's where SNS comes in. We publish to SNS which will fan out to multiple SQS queues. When a new service is built, it says to SNS "subscribe my queue to these topics". The publisher of the event doesn't know about the subscribers.
We have all services running inside a VPN (see one of our older posts: https://blog.yourkarma.com/building-private-clouds-with-amaz...) and we also use HTTP Basic token auth that are configured upon deployment. Every app gets its own token, so we can trace which app does what.
We use SQS for basically everything that happens asynchronously to the main flow. So when a user signs up there are a bunch of things that need to happen straight away (create an account, give 100MB to every new user), these go via HTTP. The others (email, give the owner of a Karma an additional 100MB and a push notification) goes through SNS and SQS.
All these async things don't impact the main flow of the user, so it's no problem that it isn't instantaneous. We are running background processes that do this.
We only use Rails for our frontend applications, they don't contain any business logic. Our backend processes are usually Sinatra for HTTP requests, or custom daemons.
Each app gets their own queue. So there is a queue for the shipment app and for the mailer app. When an event is published to SNS, it gets added to both queues.
It's easier to test individual items, for sure. Testing small code bases is the best thing ever. However, some actions require stuff to happen in multiple services.
There are "contracts" on how to talk to other services. You can test if you follow that contract, but it's hard to verify automatically that these contracts are in sync between apps.