Also, Gonzaga has built such a strong basketball brand. In 1999, they were the out of nowhere lovable Cinderella that knocked off giants and gave #1 UConn all it could take in the Elite 8. They followed that up the next year and advanced to the Sweet 16 after knocking off #2 St. John's, but they were still a Cinderella that got to the NCAAT 2 years in a row. But after making the NCAAT every year and also getting high seeds on some years which resulted in them getting the Elite 8 and then the NCAA title game twice, they are no longer a Cinderella and have not been considered that for a long time now.
In addition to what I wrote above, another thing that helps their brand is they always play tough out of conference opponents, which not only gives them more national exposure, but it gives the necessary high level competition that they did not face in the WCC.