In response to question 1, there is some subtlety involving use of the phrase "same object". This more or less immediately suggests to me the question of whether we are thinking of a bijective proof as establishing an isomorphism between structures, or not.
One of the simplest examples I can think of is the distinction between a permutation on an n-element set and a total ordering on the same set. There are $n!$ structures in each case, but in the one case we are counting the elements in a group, and in the other we are counting torsors over the same group. To see that these objects are truly distinct, imagine that we have a bijection $f: S \to T$ between n-element sets; how would we transport the structures in each case? In the total order case, we would simply apply $f$ directly to a total order $s_1 < s_2 < \ldots < s_n$ on $S$ to get a total order $f(s_1) < f(s_2) < \ldots < f(s_n)$ on $T$. In the other case, given a permutation $\phi: S \to S$ on $S$, we'd have to conjugate by $f$ to get a permutation $f \phi f^{-1}$ on $T$. These are very different actions; in the case where $S = T$, the action of $Aut(S)$ on total orders has just one orbit, and the action of $Aut(S)$ on permutations has many orbits given by cycle type decompositions.
In the language of category theory, the issue is whether a bijective proof means an isomorphism between Joyal species, or not. For example, if $Tot$ is the species of total orders and $Perm$ the species of permutations, there is a non-isomorphic bijection between them. In such cases, one must typically make a choice of standard structure in order to effect the bijection (for example, one may choose the standard order on $\{1, 2, \ldots, n\}$ to give an explicit bijection between total orders and permutations, but a choice of different order would lead to a different explicit bijection). Cf. David Feldman's answer, where choice also enters.
This is a simple example of course, but propagates more elaborate examples. Many readers here will know of Joyal's beautiful proof of Cayley's theorem (as discussed elsewhere at MO), that there are $n^{n-2}$ tree structures one can put on an n-element set. This also involves a non-isomorphic bijection between Joyal species; in compact form it involves a non-isomorphic bijection between two species
$$Tot \circ Arbor$$
$$Perm \circ Arbor$$
where $Arbor$ is the species of what Joyal calls "arborescences", in other words rooted trees. For details, consult Joyal's original article (in French) in Adv. Math. 42 (1981), 1-82. Or see the book Combinatorial Species and Tree-like Structures by Bergeron, Labelle, and Leroux (Cambridge U. Press, 1998).
Andreas Blass has an interesting paper "Seven Trees in One" where there is an in-depth discussion of issues of choice and constructivity. The paper by Conway and Doyle on 3A = 3B implies A = B also comes to mind here (this has also been discussed at MO).
