Auch wenn es preislich nicht ganz deinen Vorstellungen entspricht, könntest Du mal einen Blick auf
http://www.hosteurope.de/produkte/Virtual-Server-Linux
werfen. Finde es mit Trafficflatrate eig. ganz ok, habe selber einen Server dort allerdings in der Windows-Variante.
Thomas