I've drawn an ASCII table summarizing the proposals so far.  If I've made any factual errors I trust you'll let me know.


=<type> means os.stat().st_mtime is changed to that type.
+<type> means os.stat() grows a new field using that type,
  and the current behavior of st_mtime is unchanged.

___________________________________________________________________________

[ UPSIDES      ]        =(int,int)  +(int,int) =Decimal +Decimal =float128
[ yes is good! ]

all existing code gets   no           no        no       no       yes
more accurate for free

some existing code gets  no           no        yes      no       yes
more accurate for free

guaranteed
future-proof against     no           no        yes      yes      no*
new representations

very very
future-proof against     no           no        yes      yes      yes*
new representations

* float128 could handle representations finer than yoctosecond resolution,
  10**-24, but not another 10**-3.  fwiw, yocto is currently the smallest
  defined prefix.
___________________________________________________________________________

[ DOWNSIDES   ]          =(int,int)  +(int,int) =Decimal +Decimal =float128
[ yes is bad! ]

breaks existing code      yes          no        yes      no       no

requires new code in
order to take advantage   yes*         yes       yes*     yes      no
of added precision

requires implementing a   no           no        no       no       yes
complicated new type

* Since this option breaks existing code, obviously people will have to
  write new code in order to cope.
___________________________________________________________________________


My take on the above: if we're willing to put people through the pain of changing their code to use the new accuracy, then Decimal is the obvious winner.  I see no advantage to any of the pair-of-floats proposals over Decimal.

If we want all existing code to continue working and get more accurate automatically, the only viable option is float128 (or a multiple-precision float).