We moved our Twilio app off Heroku for the same reasons. Extensive optimizations and we would still get timeouts on Twilio callbacks.

The routing dynamics should be explained better in Heroku's documentation. From an engineering perspective, they're a very important piece of information to understand.

We're with https://bluebox.net now and are very happy.