You could try
rackshack.net. For about $100 per month (plus $100-$300 in setup fees), you will receive your own dedicated server, which includes 400 GB of monthly transfer. The servers usually have Apache and MySQL installed by default, but it would be trivial to remove them and install AOLserver and Oracle.
