The "official" definition I've always used is that reduction is the gain of electrons. IUPAC seems to use the same definition. It looks like organic chemistry books often use the addition of oxygen to identify oxidation, and the addition of hydrogen or the removal of oxygen to identify reduction. This is in line with the historical definitions (at least according to wikipedia) that defined reduction in terms of the change in mass on heating (if oxygen was lost, the weight would be reduced).
When using these shorthand rules, I think it's important to distinguish between the purposes of the definitions. The more formal "official" (according to IUPAC) definition is intended to get as close to the underlying physics as possible. The less formal "shortcut" definition used here is intended to quickly allow chemists to identify electron transfer just by looking at the structural formulas. In fact, in my copy of Wade's Organic Chemistry (4th ed) it says
Most organic chemists habitually use the following simple rules, based on the change in formula of the structure:
It then goes on to define redox reactions in terms of gain or loss of oxygen and hydrogen. This implies that the author doesn't intend it to be read as a formal definition - just a shortcut you can use in a pinch.
This is a case of "it works well enough" being used to make life easy - but it is important to remember that reduction isn't really being defined as gain of hydrogen in the formal scientific sense. It is still defined as a gain of electrons - it just so happens that in organic reactions, it is very difficult to add electrons to something without also adding hydrogen, and so the shortcut works (due to electronegativity differences between O, C, N, P, and H, as you pointed out).
Here's an example of a redox reaction where this rule won't work, but looking at electrons will:
$$
\ce{Li(s) + 1/2H2(g) -> LiH(s)}
$$
We are adding hydrogen to lithium, and the oxidation state of Li goes from 0 to +1 - it is oxidized, not reduced.
I have been looking for an example of an organic reduction that does not involve the addition of hydrogen, but haven't been able to find one - which is probably why this shortcut rule works.