Bootbox - Not recommended, need to register/transfer domain to their expensive registrar to get all the features.
Logical Hosting - Not sure, never heard of them before.
Mycgiserver - I don't think it has MySQL, even if it does, 5 megs is way too little.
Phreak.co.uk - Requires a super wierd site.
Surecity English - Never up.
Worldzone - No PHP or MySQL. No FTP for uploading the files either.
X-Mail - Not sure, never heard of them before.
Ouch, that takes out alot of choices. Perhaps you can try
http://www.spaceports.com They have unlimited space (as in starting with 20 megs and upgrading to infinity), user placable banners that pay
you 10cents per click, and MySQL on request.