Uma vez perdido, já era. Os teclados/mouses da Microsoft são pareados na fábrica e não existe nenhuma maneira de refazer esse procedimento. Eu tive um Wireless Mouse 2000 e um Wireless Mobile Mouse 4000 que eu gostava muito, mas abandonei a marca de vez após ter tido o mesmo problema com o receptor de ambos. Desde então sigo feliz com um MX Anywhere 3 da Logitech.
(inclusive esse modelo específico de receptor do Wireless Mouse 2000 é um dos que mais dá problema, tanto que abandonaram ele nos teclados/mouses seguintes)