After a little investigation I believe that the problem is likely that the Amazon server is not greeting with a 220 welcome message (as you can see from the telnet session (in orig post) that it doesn't send one). So my clients are hanging, waiting for the response.
I suppose the best solution (if I want to stick with Amazon) is to modify one of these clients. *sigh*