CALEA also requires that encrypted communications be decrypted.
True, within limited context. CALEA requires that the communication providers and equipment decrypt. If you can communicate with general-purpose equipment and networks (e.g. PCs and the Internet) where your software handles things, there currently isn't any law in the US which require it be decrypted. That is why the government wants a "CALEA II," to make it illegal for people to write or use secure software, such as ssh or gpg.
The reason Skype isn't legally allowed to be secure, is that Skype software completely relies on the Skype service, and the dedicated service both falls under CALEA and and has a single point of pressure (currently: Microsoft). If the service were something generic (e.g. use any XMPP server) and replaceable, and if the client software handled the security, then CALEA wouldn't apply. Beyond CALEA itself, governments and other powerful entities can use force against software makers, so just make sure: 1) your software is not single-source; effectively this means it needs to be Free Software 2) it uses generic networks, and the software secures things at the endpoints rather than relying on the service to magically apply security (which is hilarious when you think about it).
Skype's security problems reminds me a lot of some basic strategies for computer freedom in general. While Free Software and standardized services are usually preferred because they're most likely to not work against the user' interests (and if they do, it's almost never deliberate), there actually do exist situations where a proprietary service or application may be fairly safe. The trick is to never, ever use a proprietary application with a proprietary service, combined. As long as one or the other can be replaced, you have a means of keeping the overall system "honest" and responsible to the user.
So while, for example, the iTunes application may be a rather shittier-than-average media player, it's actually fairly safe to use it as a player. Just don't use it with the iTunes store or you're risking getting into a single-source trap. Or if the iTunes store were to opens its protocols so that other applications could transact with it, it would be just fine -- just don't use the iTunes application with it. Similarly, nearly all websites are effectively proprietary (e.g. they're not running GPL3 code) but that's totally not a problem, because your Firefox or Chromium or Konqueror lack special code to screw you over, by for example, locking you into any of these websites (or, say, by leaking session keys to third parties).
The problem with Skype is that you can't use it without the Skype network. And you can't use the network without their app. Together, it adds up to an application and network which are nearly useless, because you'll never be able to trust them. CALEA is almost the very embodiment of the general problem, written into law (!) and limited to the domain of communications. You can see echos (but they're not quite as clear) of the same user-screwing idea written into other laws applying to other domains. e.g. DMCA, which is used to tie proprietary content to proprietary players, keeping users from being able to legally do things the right way (i.e. retain the capacity to "fire" their player or provider).