> I'd bring a paystub to show the interviewer that my salary history was honest. They appreciated that. They were aware that such padding was routine.

While I agree with everything else you said, this strikes me as a poor strategy unless you have some other form of leverage with which to negotiate your salary (e.g. lots of competing job offers).