Break the broken cipher
C++, 44014022 / 164607120
 
It is in C++, uses 1 GB of memory, and took about 45 seconds to find this first pair.  I'll update the time once it finds them all.
Code below.  It first finds all pairs that generate 4 zeros, then whittles those down by simple trial (see the check method).  It finds pairs that generate 4 zeros by generating two large arrays, one which contains the first 4 low-order bytes of the state1 generator, and the second which contains the negative of the first 4 low-order bytes of the state2 generator.  These arrays are then sorted and searched for a match, which corresponds to the overall generator outputting 4 zeros to start.
The arrays are too big to store in memory, so it does the work in batches sized to just fit in memory.
Looks like the complete run will take ~12 hours.
Edit: Improved the code so it only takes ~1 hour to get all possible seeds.  Now it generates the tables into 256 different files, one for each first byte of output.  We can then process each file independently so we don't have to regenerate data.
Edit: Turns out you can generate the 256 subtables individually instead of all at once, so no disk needed.  Running time down to ~15 minutes using 256MB.
#include &lt;stdio.h&gt;
#include &lt;stdint.h&gt;
#include &lt;algorithm&gt;
using namespace std;

#define M1 65539
#define N1 4294967087
#define M2 65537
#define N2 4294965887
#define MATCHES 7

// M^-1 mod N                                                                                                                                                        
#define M1_INV 3027952124
#define M2_INV 1949206866

int npairs = 0;

void check(uint32_t seed1, uint32_t seed2) {
  uint32_t s1 = seed1;
  uint32_t s2 = seed2;
  for (int i = 0; i &lt; MATCHES; i++) {
    s1 = (uint64_t)s1 * M1 % N1;
    s2 = (uint64_t)s2 * M2 % N2;
    if (((s1 + s2) &amp; 0xff) != 0) return;
  }
  printf(&quot;%d %u %u\n&quot;, npairs++, seed1, seed2);
}

struct Record {
  uint32_t signature; // 2nd through 5th generated bytes                                                                                                             
  uint32_t seed;      // seed that generated them                                                                                                                    
};
// for sorting Records                                                                                                                                               
bool operator&lt;(const Record &amp;a, const Record &amp;b) {
  return a.signature &lt; b.signature;
}

int main(int argc, char *argv[]) {
  Record *table1 = (Record*)malloc((N1/256+1)*sizeof(*table1));
  Record *table2 = (Record*)malloc((N2/256+1)*sizeof(*table2));

  for (int i = 0; i &lt; 256; i++) {  // iterate over first byte                                                                                                        
    printf(&quot;first byte %x\n&quot;, i);

    // generate signatures (bytes 2 through 5) for all states of generator 1                                                                                         
    // that generate i as the first byte.                                                                                                                            
    Record *r = table1;
    for (uint64_t k = i; k &lt; N1; k += 256) {
      uint32_t sig = 0;
      uint32_t v = k;
      for (int j = 0; j &lt; 4; j++) {
        v = (uint64_t)v * M1 % N1;
        sig = (sig &lt;&lt; 8) + (v &amp; 0xff);
      }
      r-&gt;signature = sig;
      r-&gt;seed = k;
      r++;
    }
    Record *endtable1 = r;

    // generate signatures (bytes 2 through 5) for all states of generator 2                                                                                         
    // that generate -i as the first byte.                                                                                                                           
    r = table2;
    for (uint64_t k = (-i &amp; 0xff); k &lt; N2; k += 256) {
      uint32_t sig = 0;
      uint32_t v = k;
      for (int j = 0; j &lt; 4; j++) {
        v = (uint64_t)v * M2 % N2;
        sig = (sig &lt;&lt; 8) + (-v &amp; 0xff);
      }
      r-&gt;signature = sig;
      r-&gt;seed = k;
      r++;
    }
    Record *endtable2 = r;

    sort(table1, endtable1);
    sort(table2, endtable2);

    // iterate through looking for matches                                                                                                                           
    const Record *p1 = table1;
    const Record *p2 = table2;
    while (p1 &lt; endtable1  &amp;&amp; p2 &lt; endtable2) {
      if (p1-&gt;signature &lt; p2-&gt;signature) p1++;
      else if (p1-&gt;signature &gt; p2-&gt;signature) p2++;
      else {
        check((uint64_t)p1-&gt;seed * M1_INV % N1, (uint64_t)p2-&gt;seed * M2_INV % N2);
        // NOTE: may skip some potential matches, if p1-&gt;signature==(p1+1)-&gt;signature or p2-&gt;signature==(p2+1)-&gt;signature                                            
        p1++;
      }
    }
  }
}