I used buyvm.net for BSD a while back. Didn't have any issues, and the few times I contacted their support they were quick to respond and helpful.

rootbsd.net before that, but they don't seem to exist anymore.