Is there a method to break an EC curve for all key-pairs (Q,d) such that (Q=d*G) faster than breaking every single key-pair? Related to this question: Is there any memory trade-off that helps such attack?

Obviously if the field size is very small (say 40 bits) it´s possible, but what if the field size is 160 bits long? or 256 bits?
Well, Big-Step/Little-Step can be written as a precompute-table and then lookup type algorithm, however, it doesn't become close to practical with a 160 bit field.

Here's how Big-Step/Little-Step works; we first select two integers $a$ and $b$ with $ab \ge size(group)$ (I consistently talk about group rather than the curve; that's because Big-Step/Little-Step will apply to any finite group.  In terms of Elliptic Curves, for practical purposes we can make the assumption that $size(group) \approx size(field)$.

In the precompute phase, we construct a table with the pair of values $(ib, (ib)G)$  for $(0 \le i &lt; a)$.  This table will contain $a$ rows, and takes $O(a)$ time to construct.  Note that this table does not depend on the point $Q$ that we'll end up computing the discrete log on.

In the lookup phase, we compute the points $Q - jG$ for $0 \le j &lt; b$, and look up each of these points in the table.  If we find one of the points in the table, we have $(ib)G = Q - jG$ (where $i$ is the value in the table, and $j$ is the value we used to compute the point), we then know that $Q = (ib + j)G$, and hence we have the discrete log.  This phase takes $O(b)$ expected time (assuming each lookup can be done in constant time using appropriate data structures).

Now, the total time taken is $O(max(a,b))$; to minimize this value, we generally assume that $a=b\approx\sqrt{size(group)}$, thus giving us a squareroot time algorithm.  However, there is no such hard requirement, and if we're going to reuse the table multiple times, it makes sense to increase the value of $a$ (the one time cost) so we can decrease $b$ (the per-discrete-log cost).

However, once we start talking about a group with circa $2^{160}$ members, well, this doesn't work out.  For one, even in the balanced case, we're talking about a table with $2^{80}$ entries; that in itself is impractically large.  If we consider increasing $a$, the table size becomes even more impractically large.

Now, one obvious idea to reduce the table size is to create a Rainbow table.  It turns out that Rainbow tables will work in the way we want (allowing us to build a table that we can use to lookup $i$ given $(ib)G$ values); however, it turns out not to buy us anything.  Rainbow tables allow us to compress the table by a factor of $k$ by increasing the lookup time by that same factor $k$.  That turns out to be the killer; because the lookup phase involved $O(b)$ table lookups.  We can make the table $O(a/k)$ entries long; however the lookup phase will now take $O(kb)$ work; we haven't gained anything that we wouldn't have gotten by making $a$ smaller by a factor of $k$ and $b$ larger by a factor of $k$.