Re: Simple solution...
Congress already has the power to regulate interstate commerce, and most data traveling over the internet is interstate. Even for stuff that isn't like say an iMessage conversation with someone across town, while the actual text of your conversation is point to point and may not cross state lines, each of your phones can only find each other to begin the conversation thanks to Apple's servers.
Even if this conversation happened in California, they could be doing maintenance on their servers there and you connect to the new datacenter in North Carolina instead. The courts have always given congress very wide latitude in what is considered "interstate" commerce, so I don't think the legality of regulating just about every possible use of encryption to communicate with someone by almost any electronic means would be a problem for the government.
The issue for those wanting regulation isn't that encryption can't be regulated, it is that congress has chosen not to act. Which basically means they can't agree on the correct course of action. Some would probably support making it illegal to use any form of encryption the government couldn't break, others would want a law specifically barring the FBI from doing what they tried to do to Apple, and the majority would be at various points in between.
The government tried with Clipper in the 90s, which was fortunately shot down, and lucky for us no one thought to try to do this in the panic of all the bad legislation post 9/11 like the Patriot ACT. I guess we're fortunate that encryption was used so infrequently at the time that the illegal warrantless wiretapping was able to get enough to keep them satisfied.