• Consider each possible substitution of characters for asterisks. I'm using upper and lower-case letters, plus the handful of punctuation marks.
• Interpret each candidate as a base-91 integer. Why 91? It covers the span of possible characters in the input, it's prime, and it's 2 digits. It just seems good. I don't know if it's optimal.
• Modulus by a carefully chosen denominator. (359473561) Then check for a the existence of the result in the embedded hash array. If there's a match, that's the correct substition.

In order to verify that no incorrect result would be produced, I used a c# program to verify the output for all possible inputs. It's not very portable, and it's quite long running. I've been letting it search for more than 24 hours for candidate denominators so far, so it's not really suitable for TIO. I'm running it in Linqpad.

• Consider each possible substitution of characters for asterisks. I'm using upper and lower-case letters, plus the handful of punctuation marks.
• Interpret each candidate as a base-91 integer. Why 91? It covers the span of possible characters in the input, it's prime, and it's 2 digits. It just seems good. I don't know if it's optimal.
• Modulus by a carefully chosen denominator. (359473561) Then check for a the existence of the result in the embedded hash array. If there's a match, that's the correct substitution.

In order to verify that no incorrect result would be produced, I used a C# program to verify the output for all possible inputs. It's not very portable, and it's quite long running. I've been letting it search for more than 24 hours for candidate denominators so far, so it's not really suitable for TIO. I'm running it in LINQPad.

Stax, 749 295 bytes

â•8ZÄö╒↨)╓p▲É≤êƒ╒╞îµτ;Mge%p•╘├i⌡l→¢ë>☺~┴○╘0♂FIJk*•4æτ│☻D╣π•▄ƒ²┐☼??n¶ ○v&dA‼¢~♦·╥▐ÿµôóúΦ}↕≈+╢╔◘τ•*♣╢╡>æ∙ú▐JKY§V█á▓÷≥\─▒⌡5‼⌠↑π}φï┬h⌂O♥0▐→PO`º?¶•ⁿ☺Åì~₧)PP9Δdæz↕ixà4↓ÅV73↕─¼∙Æ∟VC┘Iül♫r⌐♀¡ÄmÇ♠O~ò°╬█ïR◘â~Σ▲}VÖ┬&┬⌂X═nå.wF`-♦↑s0öW≤┘┴♠6;♫⌂<u$µ○ºTIÆÖï╠»áπ└∟♪σx¥╥▬Zñôöi:ºg¡Σ╧Ω╜onc⌂╓jÑ1╗└¢*↑G:≤÷eφQXPKl0╥►÷ü

Run and debug it

It's possible there are some broken cases, but I will work on an explanation, verification, and further golfing later. When this is finalized, I will need some kind of organized evidence of general correctness.

Stax, 294 bytes

ê(·▲[*▬è0↑u■<pá{∞♫┼¢]$Fò╦7τ}αzoN≡ù÷♥R♪♪éé#Ä↑♂¼y>Φp←E├Tì·æ≈ßÿOÄ╩%▼Åp}∞½É÷_~ï♦♪s○╨5╓ok½♪◄}§3vimεå╩p"G4ƒs┬]K╡àbá•Ä◄E°µte\τ╚¥∞LH¥êoc▐I/♥∞íJ{σ↓⌠╢§♥]8<µ6ε∩╠ån¥←A↨⌡↨▼♠áiåcTε╛ëJv⌡♂'┬û▒╟_E2↑☺│╚ê£-vç╘▬╒ì)#Φ¼∟æ∟q⌐▀☻7w_ì~Δc'Ω∙j≡┼Γó2"äV√n◘j≤╦╓ΘiL.,▲♂▌▼∞ccñó╘î←iaΩï)NCøAP┼b_ε☺Cam╥~αDM↕Aä<₧¿é■N/╞τQ╠Γù>b^S>◘á↑

Run and debug it

Here's the approach:

• Consider each possible substitution of characters for asterisks. I'm using upper and lower-case letters, plus the handful of punctuation marks.
• Interpret each candidate as a base-91 integer. Why 91? It covers the span of possible characters in the input, it's prime, and it's 2 digits. It just seems good. I don't know if it's optimal.
• Modulus by a carefully chosen denominator. (359473561) Then check for a the existence of the result in the embedded hash array. If there's a match, that's the correct substition.

In order to verify that no incorrect result would be produced, I used a c# program to verify the output for all possible inputs. It's not very portable, and it's quite long running. I've been letting it search for more than 24 hours for candidate denominators so far, so it's not really suitable for TIO. I'm running it in Linqpad.

const string AllChars = " ',-.:ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const int Base = 91;
const int InputCount = 14252;

void Main() {
    string filename = Path.Combine(Path.GetDirectoryName(Util.CurrentQueryPath), "titles.txt");
    var titles = File.ReadAllLines(filename);
    Console.WriteLine("Original titles: {0}", titles.Length);
    Console.WriteLine("All characters: {0}", AllChars.Length);
    
    var originalHashes = titles.Select(Hash).ToArray().Dump("Original hashes");
        
    BigInteger candidateMod = 359473561; //BigInteger.One * InputCount * AllChars.Length * AllChars.Length * titles.Length;
    BigInteger? bestMod = null;
    BigInteger failJump = 1;
    
    var candidateContainer = new DumpContainer(candidateMod).Dump("Candidate");
    var bestContainer = new DumpContainer(bestMod).Dump("Best");
    var rateContainer = new DumpContainer().Dump("Candidates / s");
    
    int tested = 0;
    var sw = Stopwatch.StartNew();

    while (true) {
        bool success = TestCandidateMod(candidateMod, titles, originalHashes);
        if (success) {
            bestContainer.Content = bestMod = BigInteger.Min(bestMod ?? candidateMod, candidateMod);
            candidateMod = candidateMod * 99 / 100; // reduce by 1%;
        }
        rateContainer.Content = ++tested * 1e3 / sw.ElapsedMilliseconds;
        candidateContainer.Content = --candidateMod;
    }
}

bool TestCandidateMod(BigInteger candidateMod, string[] titles, BigInteger[] originalHashes) {
    var moddedHashes = new HashSet<BigInteger>(originalHashes.Select(h => h % candidateMod));

    bool TitleIsOk(string title) {
        BigInteger originalHash = Hash(title);
        for (int i1 = 0; i1 < title.Length - 1; i1++) {
            BigInteger placeValue1 = BigInteger.Pow(Base, title.Length - i1 - 1);
            foreach (var c1 in AllChars) {
                int offset1 = c1 - title[i1];
                BigInteger hash1 = originalHash + placeValue1 * offset1;
                for (int i2 = i1 + 1; i2 < title.Length; i2++) {
                    BigInteger placeValue2 = BigInteger.Pow(Base, title.Length - i2 - 1);
                    foreach (var c2 in AllChars) {
                        int offset2 = c2 - title[i2];
                        if (offset1 == 0 && offset2 == 0) continue;

                        BigInteger hash2 = hash1 + placeValue2 * offset2;
                        if (moddedHashes.Contains(hash2 % candidateMod)) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    return titles.AsParallel().AsUnordered().All(TitleIsOk);
}

BigInteger Hash(string title) => title.Aggregate(BigInteger.Zero, (a, b) => a * Base + b);

Another note about the storage of the embedded hash values in the program. The hashes are sorted prior to embedding in the array. I'm using a stax feature called "crammed integer arrays" which is a way of efficiently representing integer arrays. This representation is able to store differences between elements if that's more efficient, so pre-sorting the values saves some bytes.

Here's the unpacked representation with some minimal comments.

Vl" ',-.:"+:2   all pairs of replacement characters
f   filter
 ;'*/s\$1T  do replacement
 91|E   base-91 digits
 359473561% mod by denominator
 ">m\zR^ehBT}/!P*Nv:0N?s}FGN\:M.RT0r2VVm560$k;!yP<I*&R0_&q6wEcg8)&DsZ_!}&}Y&:Ngv&B::n!g6y &&eej...Z-&J..7!Rso36>y89:*iA*eNHGBmZ5!kiZ5*D(};*Xgkvwqn^(g?!kJib&g$ep!aDaA!Xw$_!w,2E.6NFG6DPat&(u4?28BIRu<bBL\S!ugPf!Ry;&T0\/^y\S{gu;!\0spo!^3!}X0l!i$L5&Z8@|!X4}p.LyU:X2M&PR6Y!k*,[F(&v&(ZJ5Jo0d!RN!hsDFvV.kI*{u@_!a<oGoqsG2}XhJ:2,"!
 #  count occurrences in crammed array

Stax, 749 304 bytes

∞C¼φç)╧.»⌐[•»Δ╢Σé☺═╒ôP←ú¶n╬æ╓h╝MR¶⌠₧┌∟&☼↕εHΩ?ⁿq>→P3▓x»♥♪`Ü-V▒╔╡b▲üæb♀╕√~♫─µ-0☼úS⌠╩ѽeV§¶u≈5Bm▓ ♣íº‼;L.╒∙b{IK▓╫½f¥ ⌠∟→╒m3eçM╠ºH?ƒ╩«↓ûÿ8ÿ▲o╘ä┴MΩ┴k₧Å♂╛ör:╥↔m╦X▐_~Ö╕s/╣¶QBóΘ@u⌐╧∙j<ñ╝╟ñ╘1ü/├a%û♀└3xU02◘H○ú█ô$øL♣│:L5t₧û£¼3√╚αcO╢mxv▄IÄÆ→♣óø│+¥»{æV╗Jr▄⌠ε↓○☺X█≡╬½╔╢&ÇMCσ☺∟⌂f┌$`8÷─╢-N►┴╥!vπß☼m-ä~3yZ╘█σ₧(^▌╥▓p2╚⌂≡ÿá

Run and debug it

It's possible there are some broken cases, but I will work on an explanation, verification, and further golfing later. When this is finalized, I will need some kind of organized evidence of general correctness. It works on the cases I've tested so far.

Stax, 749 295 bytes

â•8ZÄö╒↨)╓p▲É≤êƒ╒╞îµτ;Mge%p•╘├i⌡l→¢ë>☺~┴○╘0♂FIJk*•4æτ│☻D╣π•▄ƒ²┐☼??n¶ ○v&dA‼¢~♦·╥▐ÿµôóúΦ}↕≈+╢╔◘τ•*♣╢╡>æ∙ú▐JKY§V█á▓÷≥\─▒⌡5‼⌠↑π}φï┬h⌂O♥0▐→PO`º?¶•ⁿ☺Åì~₧)PP9Δdæz↕ixà4↓ÅV73↕─¼∙Æ∟VC┘Iül♫r⌐♀¡ÄmÇ♠O~ò°╬█ïR◘â~Σ▲}VÖ┬&┬⌂X═nå.wF`-♦↑s0öW≤┘┴♠6;♫⌂<u$µ○ºTIÆÖï╠»áπ└∟♪σx¥╥▬Zñôöi:ºg¡Σ╧Ω╜onc⌂╓jÑ1╗└¢*↑G:≤÷eφQXPKl0╥►÷ü

Run and debug it

It's possible there are some broken cases, but I will work on an explanation, verification, and further golfing later. When this is finalized, I will need some kind of organized evidence of general correctness.