I'd like to thank everyone for all the help you've provided.
We have decided to move to a dedicated server after all. It'll be a managed dedicated server, so I don't have to do the admin work.
The server will be at the same host we have now, at least until the end of the school year (because this is the least disruptive option). After school is over we can evaluate whether we are fully satisfied with the service or not and I have bookmarked RackSpace as an alternative.
The cloud computing sounds very interesting, but unless we can find a *managed* cloud computing service, I don't think it is right for us.
I'd like to thank everyone for your assistance and guidance. You have been most helpful. Especially considering that the last 2/3 of the thread were not even about Drupal.
Best regards. Daniel.