lowendbox.com lists hundreds of cheap VPS, a few of them payable in bitcoin

Often with reviews, company history etc.