They each have their pros and cons.
Out parameters are fast and cheap but require that you pass in a variable, and rely upon mutation. It is almost impossible to correctly use an out parameter with LINQ.
Tuples create collection pressure1 and are un-self-documenting. "Item1" is not very descriptive.
Custom structs can be slow to copy if they are large, but are self-documenting and are efficient if they are small. However it is also a pain to define a whole bunch of custom structs for trivial uses.
I would be inclined to the custom struct solution all other things being equal. Even better though is to make a function that only returns one value. Why are you returning two values in the first place?
Note that tuples in C# 7, which shipped six years after this answer was written, are value types and hence less likely to create collection pressure.
1 Every time you allocate a small object off the heap, that puts "pressure" on the garbage collector. The more pressure, the more frequent collections. In some applications is it important to control the amount of collection pressure produced, so allocating a few million tuples unnecessarily can be a bad thing in those applications. Of course, like all questions of performance, don't blindly make changes until you understand the magnitude of the problem.
struct
asEric
mentioned. – Baca