1) The domain i gave you is 1 of 6. They've just merged with a design company. The original domain is www.frozenmidnight.com
as far as i know.
I can only vouch for them from mid/early 2005.
Domain Name: FROZENMIDNIGHTHOSTING.COM
Registrar: ENOM, INC.
Whois Server: whois.enom.com
Referral URL: http://www.enom.com
Name Server: NS2.FROZENMIDNIGHTSERVERS.COM
Name Server: NS1.FROZENMIDNIGHTSERVERS.COM
Updated Date: 17-dec-2005
Creation Date: 20-dec-2004
Expiration Date: 20-dec-2006
2. The majority of the hosting companies i've been through were free. These include: host.sk when they were free, matrixweb, polarhome, netfirms, brinkster, hostmatrix, 101sitehosting, host.ru, bravenet, my isp (virgin.net), hostultra, namek.co.uk, x10hosting. Some were forum based - such as freehostingpartner, hey.nu, etc. I first outlayed money to sifen7.com - they offered me a cheap 1 time fee account which i use as backup - i switched away because they stopped allowing me to host a domain which i purchased after i bought them. I moved to freenukehosting - a post for host service which offered great things but didn't deliver - 3 times they deleted my account as they were a new company and inexperienced. I've also paid for 1dollar-host - they provided a great service that cost me next to nothing. The downtime was fine and I was with them for about 4 months. I got my account with FMH long enough before it was due to renew it so that I didn't have to part with them if FMH didn't work out. They did so i'm no longer with 1dollar-host.
Some of the companies no doubt have died out - but thats surely a comprehensive enough list. I've been moving from host to host for about hte last 4 years - since i started hosting a CS clan website.
3. Thanks for pointing that broken link out. Yeah I did post it on another forum and then stumbled accross this one too.
4. My domain was registered free with my hosting package. I guess it's up to them what nameservers they use.