Been using their <$5/month Atom server for quite some time now. Zero problems, and I've had months pushing 500GiB of traffic, getting full 100Mbit pretty much all the time.
Their cheapest Atom seems to be $7? It also looks like the cheapest one they have in their Canadian data center is a $21 Core i3 (which is still a very good deal, with 2 cores/8 GB RAM/1 TB HDD/unlimited traffic).
There was an offer on within the last year or so that took them down to crazy low prices. It apparently caused a lot of customer churn which is why they now do setup fees :(
Never had a problem with their service, but their pricing is all over the place
The only issue I've had with OVH and Kimsufi servers was that any incoming or outgoing SSH connections would also terminate on the first connection attempt. Always. Mac, Linux, Windows - it didn't matter. I've never had this issue with any other host.
I got so annoyed with it that I created a simple bash script that would attempt to connect, pipe the results to /dev/null and then connect again. Always failed on the first attempt, always worked the second. Their support weren't able to help me either.
The only upside was that it forced me to add decent connection error-handling to my scripts.