Based on your experience, do you guys have any idea if a simple hosting server is enough to run a newsletter with 10K subscribers or do I need to go for a dedicated server (or any other alternative solution)?
What mostly matters is the service you use to send email. You you want to spend money, do not change the hosting provider, bu get an account on mandrill (for example) and use it to send your newsletters.