B737NG flight crew abandoned a CAT 3 ILS approach when they belatedly became aware the procedure is NOTAM'd out of service.

Narrative

The safety system of checks and balances failed us on flight to HOU. I missed a critical NOTAM; but in my opinion; I was set up and not backed up by the FAA; ATC; and our company. As a result; I commenced a CAT 3 approach; which was not available; to Runway 4. Dispatch assigned an alternate of ZZZ for this flight based on fog and haze in the METAR and TAF; though the visibility was not forecasted to go below 6sm. Enroute to ZZZ when we got the ATIS; visibility had lowered to 1 mile and ILS Runway 4 was in use. As we got closer; the visibility continued to drop and at one point got down to 400 FT Runway Visual Range (RVR). Approach Control asked us what our minimums were and we responded with '700 FT.' (Our mins were actually 1800 FT had we seen/known of the NOTAM.) We slowed down for our vectors and I sent an ACARS message to Dispatch to let them know the current RVR. Shortly the visibility increased to around 800 FT and then varied. I again sent an ACARS to Dispatch and told them ZZZ was 'back up.' I then received a message from Dispatch assigning a new alternate of ZZZ1 with a lower divert fuel; which I accepted. Company policy is for us to monitor company frequency on the ground (airborne only if ACARS is inoperative). My habit/technique; though; is to monitor company frequency airborne as well. I bring this up because eventually this technique prevented a bigger problem and/or safety hazard. While being vectored for the ILS final; I heard a conversation on company frequency. At first I couldn't tell if it was between Operations and the flight behind me or with Dispatch. Later I discovered it was between the flight behind me and their Dispatcher. In any event; I heard the flight behind being told there is no CAT 2/3 for Runway 4; and this is probably stated a couple times. Hearing this; I check the date on my chart; reconfirm it with my First Officer (NOTE: we had gone from briefing a Cat 1; to a Cat 2 to finally a Cat 3 as the RVR deteriorated). We both had the same page date as previously briefed. This confirmed for me that we had current charts. I made a comment to the other company flight Captain that I had a current CAT 3 approach plate and planned on flying the CAT 3 to Runway 4 and he replied he was too. We continued with our vectors for the approach. (By the way; I believe we are the 'leading edge of the spear' after the visibility dropped below CAT 1 mins.) Approach Control cleared us for the ILS Runway 4 and turned us over to Tower. Tower asked our minimums and again we reply with '700 FT.' Tower then clears us to land. Passing the final approach fix Tower states the RVR is '800 FT and dropping rapidly.' Below 1000 FT AGL I again hear the conversation about no CAT 2/3 to Runway 4. I do not recall now if I asked the other Dispatcher about this on company frequency or just heard the discussion. Regardless; I became uncomfortable with the entire situation and decided a go-around was in order so we could clear up the confusion. I said the same to my First Officer and directed a go-around somewhere around 400 FT or 500 FT AGL. Tower asked the reason for our go-around and I told them we were being told there was no CAT 3 to Runway 4. We got no response on that subject. Later while in holding with Approach Control we were again asked the same question. The Controller said he assumed we went around because of the fog; and again we replied it was because we were hearing there was no CAT 3 to Runway 4. Again no reply. After approximately 30 minutes of holding; we diverted to ZZZ2 (ZZZ1 went down). Once on the ground I called my Dispatcher and asked what was going on. The only NOTAM I had seen was an amendment to the LOC Runway 4. My Dispatcher told me there was a NOTAM for Runway 4 CAT 2/3 being unavailable. As he's telling me this; I'm looking through the 3 pages of NOTAMS and not seeing this and I tell him the same. After; literally; a couple minutes of this he finally talked me onto the correct page and just about has mecount down so many lines until there it is. Below several previous NOTAMS on manholes; reduced safety areas and an open trench is 'ZZZ NAV Runway 4 ILS Cat 2/3 Unavailable.' Below that was a NOTAM on lights being out on an Obst Stack. So sandwiched between essentially meaningless NOTAMS for pilots; was a critical one for an ILS approach. Where the checks and balances failed: FAA: The current NOTAM package is numbing and ineffective. Why do we bury important NOTAMS for flight safety in the minutia? Obviously the pilots behind me hadn't seen this either; nor pilots I spoke with later. NOTAMS need to be prioritized in order of importance and safety from the 'pilot's perspective.' I care a lot more about ILS restrictions than I do a safety area being 400 FT versus 500 FT or lights being out on a stack. Yet they are all lumped together and somehow with everything else we need to do as airline pilots; we're expected to weed through the ants to find the elephants. Elephants will kill you; ants are an annoyance. The 'numbing effect' of sifting through the unimportant to find the important creates a safety hazard. ATC: It is my belief Approach Control and Tower were not aware of the NOTAM either. If they were; I do not understand why they would clear me for an approach and to land when the weather is below anyone's CAT 1 minimums. We told both agencies our minimums and one would think if CAT 2/3 were not available; they would have said something. It's as if I tell them my mins are 0; they'll wash their hands and clear me. Secondly; if Tower isn't going to say anything about restrictions; then when the weather deteriorated and Runway 4 was put in use; why wasn't the CAT 2/3 restriction included in the ATIS to help the Aircrews? Company: Why did I never hear from my Dispatcher on the CAT 2/3 restrictions? I had sent 2 ACARS on the RVR yet was never reminded that CAT 2/3 was not available. All I received was alternate change information. Yet another flight's Dispatcher was calling to alert them. Had the other flight's Dispatcher said the CAT 2/3 was 'NOTAM'd out' versus 'there is no CAT 2/3 to Runway 4;' the picture would have been clarified much sooner. We interpreted what he was saying as there was no published CAT 2/3 to Runway 4; yet we were looking at the approach plate. Again; why is one flight getting Dispatcher warnings and another flight not? As a side note; I ran into another crew later in the day that also got delayed going into ZZZ due to the fog. They stated they received an ACARS message warning of the CAT 2/3 limitations. (They also stated they had not seen it in the NOTAMS.) The pitfall sometimes of being the 'leading edge of the spear.' Luckily; we did not attempt to land out of this approach and make the situation worse. The only reason that happened was because I monitor company frequency in the air. Had I not; after missing the NOTAM; Approach Control clearing me for the ILS with RVR at or below 1000 FT; Tower clearing me to land with RVR 800 FT and dropping rapidly; I would have landed out of a CAT 3 approach to Runway 4 (visibility permitting).