Do NOT go with newsdemon if you want to pay by PayPal, they recently moved all customers who use paypal to differnet servers (
http://www.newsdemon.com/ppgroups.php) and from what I have heard the paypal servers are VERY bad

The main server (for worldpay and credit card customers) however is pretty good (well, when I tried it a few months ago)
NewsHosting did do paypal a while back but I think they have stopped it (it was never listed on the newshosting site though) but email them and see if they are doing it again now
Also for those who dont know NewsDemon is a reseller of newshosting, just do a trace on news.newsdemon.com (type tracert news.newsdemon.com in command prompt) and you should eventually get to a server with the name newshosting in it