Earlier quoted context omitted.
This is incorrect - you can absolutely host in EC2. Our two skills are running off of a single EC2 micro instance. There is one really weird thing where you can't use US West to do an Amazon Lambda passthrough to your server, but as far as I know EC2 instances in any region should work for Alexa to call out to.
I'm sure that the issue can be fixed so it might have been. But I have the mail conversation here (10 people at least and dozen of back and forth). This was 2 months ago and I gave up on it for this specific reason.
That said, I'm curious how you managed to get an email conversation going with the team - the whole crux of the original article by Lawrence (and the forum thread which it cites) is that there's no way to have a direct conversation with anyone representing Alexa, so certification is a crapshoot.