The underlying problem here is that a single state in time is used to determine which edge of the block was hit first by the ball. But "first" and "second" is an ordering criteria in time. The higher the relative speed (i.e. the delta movement distance since last collision determination) the less reliably can the penetration depth be used.
I don't know whether a trick exists to do the job in a clever way. In general, if you determined that the objects do collide now, you have to rollback time, so shift the objects back to their respective positions to where collision just began, and then check for the edge that was involved (considering the case that actually the corner was hit).
I assume the following situation: One object, the ball, can be described as a moving circle. Its position is given w.r.t. its center, and its radius is known. The other object, the paddle, can be described as a moving rectangular, axis aligned block. It position is given w.r.t. its center, and its width and height are known. During a single time step, both movements can be assumed to be linear (straight and not accelerated).
Let t1 denote the current time and t0 the time valid at the previous time step. Let pb(t1) and pb(t0) the corresponding positions of the ball. Let pp(t1) and pp(t0) the corresponding positions of the paddle. By time normalization
k := ( t - t0 ) / ( t1 - t0 ) so that 0 <= k <= 1 within the last time step,
we can say
pb(k) := pb(t0) + k * ( pb(t1) - pb(t0) )
pp(k) := pp(t0) + k * ( pp(t1) - pp(t0) )
The task is now to compute that k where the first collision takes place. A little trick here is to separate both spatial axes. That reduces the problem, because now we have 3 collisions between a point and a line segment in 1D. To do this we first define the positions of the 4 corners of the block using its width w and height h as:
ctl(k) := pp(k) + [ -w/2 +h/2 ]T
ctr(k) := pp(k) + [ +w/2 +h/2 ]T
cbl(k) := pp(k) + [ -w/2 -h/2 ]T
cbr(k) := pp(k) + [ +w/2 -h/2 ]T
Now, for example let's say that from the above we calculate the left edge of the block as line segment in 2D
el(k,f) := cbl(k) + f * ( ctl(k) - cbl(k) ) = cbl(k) + f * [ 0 h ]T w/ 0 <= f <= 1
so that its x component is just
xl(k,f) = xbl(k)
For the same k, the x component of the point of the ball that collides first is the rightmost point on the circle, i.e.
xcr(k) = xb(k) + R
where R denotes the radius. Now compute the k' by solving
xcr(k') == xl(k',f)
and check for condition
0 <= k' <= 1
If the condition is violated then the edge is not hit and hence not considered further. Otherwise compute f' by using k' from
xl(k',f') = ...
and check the condition
0 <= f' <= 1
If the condition is violated, then the left edge is not the one touched first and hence not considered further. Although … if you want to check for collision with the corners, you should use a less strict condition, i.e. with a small positive tolerance value d, something like
0 - d <= f' <= 1 + d
Do the above analogously for the right and top edges, too. (I assume that the bottom edge plays no role.) Then the overall result is a set of 0, 1, 2, or 3 values of k'. If the set is empty then there is no collision. Otherwise the source of the minimal k' in the set tells you which edge was hit first. If the minimal k' and the next greater k' are very close (compared to a defined limit), then the ball should be considered to hit those corner of the paddle to which the source edges of both k' belong to.
Oh dear! I should stop writing such long posts … well, hopefully it helps to at least understand the problem behind the problem ;) Notice that the above resulted from mental work, so check twice for correctness if you actually want to use it.