Alle 3 de oplossingen die de TS in zijn OP aanbrengt zouden prima kunnen.

Een VPS en dedicated server zal toch moeten worden beheert, ik weet niet in hoeverre je dit zelf kan (en wilt, ook een erg belangrijke), maar dat kan tricky zijn als je niet zeker weet wat je doet.
Voordeel van een VPS / dedicated server is dat jij de enige bent die erop draait en alle resources in gebruik kan nemen.

Een shared omgeving is leuk, mits het goed is ingericht (stabiel, snelheid, etc.). Het fijne hieraan is dat je dan zelf geen omkijken meer hebt naar bepaalde zaken (back-ups, server crashes en storingen). Het enige wat je moet doen is op zoek gaan naar een goede, uitgebreide magentohostingpakket wat aan jouw eisen voldoet.

Ik, als ik jou was, verschillende bedrijven vragen om offertes en de mogelijkheden qua stabiliteit, groeimogelijkheden, back-up en fail-over en natuurlijk onderhandelen over de prijs.
En natuurlijk ook in hier op WHT in het 'Aanbiedingen gezocht' deel een topic openen en kijken of daar interessante dingen uitkomen.