You voided the check, so now you still need to pay the rent.
This is an area of law called "Mitigation of damages" -- everyone has a duty to prevent loss. Mainly, this shows up when you break a lease. You lease to December but on March 1, give notice for April 1. If you tell him ASAP, and he must make fair effort to find a new tenant ASAP. Once the other tenant starts paying, you're off the hook.
So under mitigation of damages, when the landlord told you he'd lost your check, he had a legal obligation to tell you to stop-payment ASAP, and you had a legal obligation to do so. If either of you failed to do so, then the money loss would be that person's. If he failed to notify you and the thief got your rent, you don't owe any more. If he notified you and you failed to stop payment, you would pay double rent, first to the thief, then to the landlord.
If you lose your paycheck, you can ask for a reprint
Many people presume you are a greedy, selfish individual looking to take advantage. I don't presume that. I worry that you have a wrong idea about the financial system, and you think it swings both ways.
Test question: If you dropped your paycheck in a mud puddle, do you now need to suffer 2 weeks' loss of income?
Answer: NOPE! Just like the landlord did: contact payroll immediately, tell them the check was lost, and ask for a replacement check.