You can search for trademark registrations and status at
http://tess.uspto.gov/bin/gate.exe?f...ate=mkrba0.1.1
As for your example, there are currently no registrations which include the words "adult hosting".
I don't think you'd have a problem. In some instances they will disclaimer common words or phrases. For example, in my registration for "persian kitty's adult links", they included a disclaimer that I made no claim to the exclusive right to use "adult links".