Your question is framed too generally as there are many variables when it comes to running marketing on specific solution.
Is the company you are working for new or established with clients?
Is dedicated hosting a brand new offering or are we just talking about new server(s)/specs?
Which market are you targeting?
Do you currently have VPS hosting as a product?
Have you tried any of the available advertising avenues so far?
Define tasteful.
Generally-speaking, there are plenty of things you can do: send out an announcement, promote across social media (for your target market), sponsor a local event, cold call/email, work towards creating relevant content, run traditional ads within your market, etc.