Rainbow tables and blowfish
How many starting keys should I choose?
  


The answer lies in the storage size and lookup time in the table. For example; if we split the $2^{40}$ into $t$ and $l$, the size of the chains and the number of chains, respectively. Let say $t = 2^{20}$ and $l = 2^{20}$


$t = 2^{20}$ chains;


Storage: $2* 64 * 2^{20} = 2^{27}$-bit that is $2^{21}$-Byts storage size.
Sorting: Only once you need to sort the $2^{20}$ chains ends by $\mathcal{O}(n\log n )$ time is $\approx 20*2^{20}$
The lookup time: at most for $2^{20}$ chains we have $2^{20} *\log_2(2^{20})$ by binary search.



You can use this site to calculate the parameters.


  
  If I just use N/k, my intuition would be that all the keys should end up being tested in one chain, but can we be sure of that?
  


No, we can not be sure about this. 


  
  To me blowfish is bijective (since reversible) on the plaintext, but how can I be sure that two keys won't give the same encrypted text?
  


There is no problem in the password cracking case; you found a valid one.


  
  What reduction functions should I use? It seems to me like this would play a crucial role in making sure that all of my search space has been done.
  


$(H(k_{i-1}+i))$, $H$ is a hash funtion,  $k_{i-1}$ output of the previous node in the chain, $i$ the $i$-th node. Strip the $H$ to 64-bit.


  
  If the two assumptions above don't hold, is there an efficient way to know which keys still haven't been tested to make sure they are used to generate new chains?
  


Other than storing them, no.