También creo que un VPS te serviría, y te saldría más barato.
Si todavía quieres un dedicado mira en webhostingtalk.com, tienen dos subforos sobre dedicados, uno general y otro con ofertas. Este mensaje por ejemplo:
Where to find reliable servers for 30-40$ ?
http://www.webhostingtalk.com/showthread.php?t=630494
Es muy reciente y lista varios proveedores. Por supuesto su calidad es cuestionable, pero para lo que quieres igual te sirve.