>Could it be that the definition of faster includes the time to transmit the resulting data set? In that case, if UNION ALL results in (say) 1,000,000 records while UNION results in only 5000 the transmission time for the 995000 extra records is more than the time to filter them?
Yes, I think you nail the possible problem.
If it's not broken, fix it until it is.
My Blog 
