I think I've got something, but it's ugly and I don't know how to tidy it up. Consider whether any two bags have the same number of coins in them. Exactly one of the following is true:

a all bags have 125 coins.

b 3 bags same, 1 different.

c 2 pairs of bags.

d A pair and two distinct.

e All distinct.

There is only 1 possibility for a.

For b, 500/3 = 166 (rounded down), so there are 166 possibilites (+1 for 3 empty bags, -1 for case a)

For c, the pair with the least coins could have between 0 and 124 each, so 125 possibilities.

Now it gets ugly. Suppose we have a string of 500 0s and 2 1s. For every pair of 0s, put 1 coin in each of the first two bags until you reach the first 1. Then put a coin for every 0 into bag 3 until you reach the second 1, then put the remaining coins in bag 4. Now there are 251 choose 2 strings (=125*251) where both 1s occur in an odd position, so these are valid; and there are 251^2 strings where one is in an even and one in an odd position. In (251/2)(251+1) (=126*251) of these the odd one occurs first so these are also valid. This gives 251^2. However among these strings, 1 falls under case a; 2*166 fall under case b (3rd or 4th bag same as 1st two); and 2*125 fall under case c (larger pair could be 1&2 or 3&4). The order of the 3rd and 4th bags doesn't matter, so the remainder of the strings occur in equivalent pairs. This gives a total of [(251^2 - 1)/2 - 166 - 125] for case d, and a total of (251^2+1)/2 overall.

Finally, most of the possibilities are in case e: this time we have a string with 500 0s and 3 1s, with the obvious interpretation. There are 503 choose 3 (=167*251*503) of these. However amongst these 1 falls under a, 4*166 under b, 6*125 under c and 12*[(251^2 - 1)/2 -166 -125] under d (consider possible orders of bags). The rest occur in equivalence classes of 24.

So we have a grand total of {167*251*503 - 1 - 4*166 - 6*125 - 12*[(251^2 - 1)/2 - 166 -125]}/24 + (251^2 + 1)/2.

I think this is [167*251*503 - 1 + 8*166 + 6*(251^2 + 128)]/24, but I've probably made some mistakes along the way, and don't really want to simplify this expression any more. My calculator says 894348; does this sound right?

I'm sure you came up with a more elegant method than this!