We host our own forum on a server that houses multiple websites. The code is customized heavily from a forum that was written originally (2001) by a guy named ACMLM. We've diverged pretty far from the original code at this point, and you would need root level access to a server in order to get this setup to work anywhere else due to the multiple cron jobs, xml feeds, and custom stuff going on behind the scenes.
Your best bet is to find hosting with a message board solution that they support. Many php based hosting companies will throw in phpBB or something like it for free along with their package.
Since we don't use these services, I can't really suggest one, but 1and1.com seems pretty cheap and a friend said some good things about them. I think they offer phpBB but you'd need to check their site.
Yea, but the steps they have you doing are pretty simple, and the first thing they all recommend is checking to see if you're out of disk space. Boot up in safe mode and see if the kids just filled up the hard drive.