The way my bank works, the fee for a stop order for a check is only applied if someone tries to cash the check. If it really is lost, you don't get charged, in other words. Or at least that's the way it has worked for me when I've needed to stop checks.

I like the idea of just writing another check, and having the original going toward next month's rent when and if it shows up.