Answer
Check that the outbound Routing Rule includes at least one content-based condition — a Routing Rule with no conditions defined at all can fail to match/route the outbound message properly, producing exactly this 'No valid routing rule found' error even when the sender and routing address setup otherwise look complete. Adding a content-based condition to the rule (even a simple one, if you're still just testing basic connectivity) resolves it.