Your minimum and maximum serve as a great jumping off point for the question. We can put an instant upper bound on the answer using those two figures - 4,444 possible options, narrowed down just from that list.
Let's take the minimum and work from there:
55,555
5|5|5|5|5 (easier for me, at least, to see it with some pips between the digits)
We know we can't decrement either the first or the second number, but we CAN increase the second number, so lets think of it like that. We don't actually care about WHAT the number is so we can abstract that away:
A (5) | B (5,6,7,8,9) | C (5,6,7,8,9) | D (5,6,7,8,9) | E (5,6,7,8,9)
Now we have our list of permutations. Let's see if we can find a pattern to work with so we don't have to just sit and count all that much. The first thing I notice is that this isn't so bad if we do "matching", like this: (I'll show what digits I'm "counting" in bold)
A (**5**) | B (**5**,6,7,8,9) | C (**5**,6,7,8,9) | D (**5**,6,7,8,9) | E (**5**,6,7,8,9)
A (**5**) | B (**5**,6,7,8,9) | C (**5**,6,7,8,9) | D (**5**,6,7,8,9) | E (5,**6**,7,8,9)
A (**5**) | B (**5**,6,7,8,9) | C (**5**,6,7,8,9) | D (**5**,6,7,8,9) | E (5,6,**7**,8,9)
A (**5**) | B (**5**,6,7,8,9) | C (**5**,6,7,8,9) | D (**5**,6,7,8,9) | E (5,6,7,**8**,9)
A (**5**) | B (**5**,6,7,8,9) | C (**5**,6,7,8,9) | D (**5**,6,7,8,9) | E (5,6,7,8,**9**)
A (**5**) | B (**5**,6,7,8,9) | C (**5**,6,7,8,9) | D (5,**6**,7,8,9) | E (**5**,6,7,8,9)
...
What jumps out at me here - to increment one in "D", we must iterate through 5 possibilities in "E". So, if it's just two "variables" (D & E), we'll have 25 different combinations, 5 combinations for each possible value we can take in D. Well, wouldn't a similar principle apply when considering C? Let's draw a smaller diagram with three variables to see what's at play here, something like:
A (0) | B (0,1,2) | C (0,1,2)
\-------
A (**0**) | B (**0**,1,2) | C (**0**,1,2)
A (**0**) | B (**0**,1,2) | C (0,**1**,2)
A (**0**) | B (**0**,1,2) | C (0,1,**2**)
A (**0**) | B (0,**1**,2) | C (**0**,1,2)
A (**0**) | B (0,**1**,2) | C (0,**1**,2)
A (**0**) | B (0,**1**,2) | C (0,1,**2**)
A (**0**) | B (0,1,**2**) | C (**0**,1,2)
A (**0**) | B (0,1,**2**) | C (0,**1**,2)
A (**0**) | B (0,1,**2**) | C (0,1,**2**)
This approximates your question, just is a little smaller so we can see it all spelled out. I kept the A = 1 option factor, but as you might guess by this point, it's pretty irrelevant. So, we get 9 total permutations that work for us, and through the bolding, I think it's pretty clear to see we arrive at 9 because B has 3 options, which themselves are each mapped to 3 options, so 3\*3 = 9. And indeed, in our original question, 5\*5 (when considering only D & E) gives us 25 options which conclude the totality of those two columns. So let's apply this principle again to our bigger question:
A (5) | B (5,6,7,8,9) | C (5,6,7,8,9) | D (5,6,7,8,9) | E (5,6,7,8,9)
1 \* 5 \* 5 \* 5 \* 5
625
Now, to be a little more precise, your question was what is the probability, so it'd be 625/65,535, or 125/13,107
