We can ask whether there is a "canonical" 1-1 correspondence. Here's a case where there are 1-1 correspondences but where it seems that none are canonical. Consider a vector space X of dimension n over a finite field. Also consider its dual space X* and its double dual X**. X has a canonical isomorphism F with X**, namely F(x)(f) = f(x), but it doesn't seem to have a canonical isomorphism with X*.
Therefore, a proof that X and X* have the same number of elements wouldn't be as natural as a proof that X and X** have the same number of elements.
In practice, most vector spaces come equipted with a "metric" (non-degenerate bilinear form) < , >. In this case there is the natural bijection from X to X* given by x-> f_x where f_x(y) = <x,y>.
Does this phenomenon account for the fact that it is so often easier to establish that two sets are equipollent than to establish an elegant 1-1 correspondence?
Is the question discussed in the literature on cominatorics?
This is the life blood of a lot of combinatorics. A common question is to find a "bijective proof" between two sets which are known to have the same number of elements. The book "Constructive Combinatorics" by Dennis Stanton and Dennis White devotes considerable energy to establishing "listing algorithms" and their inverses. For example, they exhibit such a bijection between {1,2,..., n!} and the set S_n of all permutations on the n-element set {1,2,...,n}. They also give bijections for set partitions, integer partitions, etc...