It is. When I posted my comment, Google voice was the main example I was thinking of (but certainly not the only one). The fact that you don't know about it is part of the problem. It'd easily be on the top of the app store lists if it was available. It just goes to show that because of Apple you don't even know what you're missing.
Your VLC example doesn't make any sense. You can watch whatever illegal movies (and illegal music) on your iPhone all you want using the built in software. You'll never get VLC, not because of anything illegal, but because "it duplicates functionality already existing in the phone". That's it.