Finding differentials and space complexity In Differential Cryptanalysis of DES-like Cryptosystems by Biham and Shamir, they provide examples using differentials inputs such as $\Omega_p = 00\ 80\ 82\ 00\ 60\ 00\ 00\ 00_x$. Most of article is about differential cryptanalysis and presents the generic method, the way to find subkeys. But I can't find a clear explanation about how to find the differentials used in examples.
I do get the idea about feeding an S-box in order to retrieve the differentials, but these S-boxes only have 6-bit inputs for 4-bit outputs (in DES). So the memory space required in order to do such analysis is $2^6 \times 2^4 = 1024$ integers $\approx 4\ Ko$. This can be easily placed in the RAM. The method is presented in Modern Cryptanalysis (2008, Wiley Publishing; Chapter 4, pp. 122-145) by Christopher Swenson.
However, given an S-box with a bigger input such as the one used in FEAL-X (while remaining broken), we need a table of the following given size : $2^{32} \times 2^{32} = 2^{64}$ integers $\approx 2^{32}\times 16\ Go$. Such a thing is too big to store on one of today's computers.
Hence my question: how is it possible to find the right differential for bigger input round functions without the size constraint of this analysis.
If such a large Sbox with no structure were to be analysed you'd treat the analysis as a one-off precomputation. 

Considering only classical differential cryptanalysis as an example, after the precomputation you'd only need to keep track of the highest probability differentials since if you combine a high probability differential with a low probability one, you've already lost quite an edge and over multiple rounds your attack will fail.

As for FEAL, there is lots of structure in the 32x32 round function and divide and conquer is the way to go.

If there was a randomly chosen huge Sbox, life would be difficult, but it is also difficult for the designer who'd have a hell of a time proving the strength of his/her randomly chosen Sbox, with any kind of guarantee. Blowfish Sboxes which are key dependent, for example, are only 8x32 (thanks @J.D.) and this helps by limiting the number of input differences that need to be considered.