Step 0: Do this if you believe in miracle: Go to your local office, ask them any information they may have on your package. Normally, there's nothing they can do as the mail man most probably already forget what happen on that day. Don't cling on your hope and drag on for too long. Proceed to step 1 as soon as possible.
_ Week 1:
Step 1: Email CIC right away to let them know your case. In the email be sure to include your personal case info (name, birth date, UCI, case #, address, phone, email, etc.) and your situation (lost CoPr before landing, need to have CoPr again and the counterfoil of 1-time IMMIGRANT visa restamped on your new passport).
Step 2: You need to file a lost report to Canada Post right away. Ask to have a ticket opened. (told them you buy both envelopes so you have the right to open a ticket, otherwise they will told you to contact CIC to open a ticket with them since only senders can request a ticket). Keep the ticket number on hand. Screen cap the delivery info online and save them somewhere.
Wait for 5 business days.
_ Week 2:
Step 3: A week has passed from when your ticket is open. Call Canada Post again and ask for result. Normally, they won't do anything. Confirm with them that your package was lost by canada post, aka they can't find it. (Be sure to keep this ticket number on hand.)
Step 4: Go ahead to report your case to the Police since you give Canada Post a week already. Get a case number from the police.
Step 5: Call to CIC call center, let them you your case. They will offer useless advice such as you need to email the CIC (which you already did) and wait for their reply).
Step 6: Collect needed documents and apply for a new passport. You may need to submit the police case number.
Wait another 5 business days
_ Week 3:
Step 7: Now, it should be 1/2 month from your first email. Write CIC another email, same content but with added information such as Canada Post ticket number, police case number, and when you should receive your new passport.
Wait another 5 business days
_ Week 4-5:
You should receive your new passport by now. If not, I'm not sure but I will suggest you go ahead because we can't wait any longer. Now it should be 30 days from the date you send your first email to CIC.
Step 8: Have your new passport on hand.
* Call up your MP (Member of Parliament), and say you want to ask for help, schedule a meeting. The secretary lady/man will ask you what is this about. Told them your situation.
* They are very nice people (at least the lady who helps me is very nice). And will ask you for the ticket number with Canada Post, the police case number, if you phone the help center or not (Step 5), if you already send email to CIC (step 1), etc.
* Told them you already call the call center, and they tell you to write email to CIC and wait for it. And you already wait 1 month since you first send email, and still get no reply from CIC.
* The lady will gladly assist you from then on. She will need a few days to contact CIC, and let them know about your case.
* She will ask you for supplements such as scanned new passport, emails to CIC etc. Give/forward them all to her, including the delivery screen caps to let her know you are not at fault here.
* Someone from CIC will personally contact you, and ask you to resend your passport.
* Remember to buy the signature option for both way this time. It will take them 1-2 days to reprint your document.
* Get back passport with CoPr + 1 time IMMIGRANT visa counter foil. Go to border. Done.
Things may change, you may get replies from CIC midway or it may take longer to reissue your stuff, but in my case, everything went very fast after I contact the MP.