I'll be damned, I figured out the source of the issue today.
I modified the values of the "MsExchangeMailboxReplication.exe.config" in order to speed up MoveRequests and ExportRequests. The config file actually states which values are valid:
<!-- Mailbox Replication Service configuration
Setting Name - Default, MinValue, MaxValue
MaxActiveMovesPerSourceMDB - 20, 0, 100
MaxActiveMovesPerTargetMDB - 20, 0, 100
I set the value for both MaxActiveMovesPerSourceMDB and MaxActiveMovesPerTargetMDB to "200", which was outside the allowed range. After reducing both these to 100 and restarting the service, everything works again.