The NASA/IPAC Extragalactic Database (NED) has deployed a new rule-based cross-matching algorithm called Match Expert (MatchEx), capable of cross-matching very large catalogs (VLCs) with >10 million objects. MatchEx goes beyond traditional position-based cross-matching algorithms by using other available data together with expert logic to determine which candidate match is the best. Furthermore, the local background density of sources is used to determine and minimize the false-positive match rate and to estimate match completeness. The logical outcome and statistical probability of each match decision is stored in the database, and may be used to tune the algorithm and adjust match parameter thresholds. For our first production run, we cross-matched the GALEX All Sky Survey Catalog (GASC), containing nearly 40 million NUV-detected sources, against a directory of 180 million objects in NED. Candidate matches were identified for each GASC source within a 7.5 arcsecond radius. These candidates were filtered on position-based matching probability, and on other criteria including object type and object name. We estimate a match completeness of 97.6% and a match accuracy of 99.75%. MatchEx is being used to cross-match over 2 billion catalog sources to NED, including the Spitzer Source List, the 2MASS Point-Source Catalog, AllWISE, and SDSS DR 10. It will also speed up routine cross-matching of sources as part of the NED literature pipeline.