Pues está Leaseweb, alguna vez use una VPN de ahí y además algunos conocidos tenían seedboxes y str0 servers ahí mismo:
http://www.leaseweb.com/en aceptan pagos por paypal y es de lo mejorcito que hay.
hostso.com tiene datacenter en usa así que no es muy seguro.
Y pues pocos son los que tienen problemas por eso (ojo que hay quien es encarcelado por eso), por lo general no pasa de que te cancelen el servicio y te congelen la base de datos.
Pero igual creo que no es recomendable lo que quieres hacer ya que megavideo es muy fácil de usar y no te quitan los videos tan rápido como en youtube. Además de que necesitaras un gran desembolso por que no sirve un hosting compartido (o por lo menso no por mucho tiempo).
Y creo que ya hable mucho y nos vayan a sancionar por hablar de piratería
