Solution:

a. The longest possible gap has length $1112$. There are four valid examples of two ultra-even years that far apart with no ultra-even years between them: $888$ to $2000$, $2888$ to $4000$, $4888$ to $6000$, or $6888$ to $8000$. ($8888$ to $10000$ is not acceptable as $10000$ is not ultra-even).

To see that no longer gap is possible, note that if $A$ and $B$ are ultra-even years between $1$ and $10000$ with no ultra-even year between them, and $B-A \geq 1000$, then $A$ and $B$ must have different digits in their "thousands place". Since both of these digits must be even, that means there must be at least one odd digit $d$ in between them, and so all the years between $d000$ and $d999$ must be in the gap between $A$ and $B$. But the smallest ultra-even year greater than $d999$ is $e000$ (where $e = d+1$, of course), and the largest ultra-even year less than $d000$ is $c888$ (where $c = d-1$), so this gap must be of length exactly $1112$.

Another approach is to consider the increasing sequence of ultra-even years: $2$ (the smallest ultra-even year), $888$, $2000$, $2888$, $4000$, $6000$, $6888$, $8000$, $8888$ (the largest ultra-even year less than $10000$). Every ultra-even year is either in this sequence or lies between two elements of this sequence, so any two ultra-even years with no ultra-even years between them must have a difference that is less than or equal to a difference between two consecutive elements of this set; but the largest such difference is $1112$.

b. The second-shortest possible gap is $12$. Examples include $8$ to $20$, $4268$ to $4280$, etc.

To see that this really is the second-shortest possible gap, note that every gap must be even, since the difference between any two ultra-even years is even. There are certainly many gaps of length $2$ (from $4022$ to $4024$, for example). We must show that there are no gaps with lengths $4, 6, 8$, or $10$. Any ultra-even year whose units digit is $0, 2, 4$, or $6$ is $2$ less than another ultra-even year (since adding $2$ to this year won't change any other digit). So if an ultra-even year is the lower year of a gap longer than $2$ years, its units digit must be $8$. However, if year $A$ is ultra-even, and has a units digit of $8$, adding $2, 4, 6, 8$, or $10$ to it will result in a year whose tens digit is one greater than the tens digit of year $A$, which will mean the new number is not ultra-even. So $12$ is the smallest possible value for the gap between such years $A$ and the next largest ultra-even number.