Today I received an email from USCIS, I was wondered why I still got email from them??? I think my case is completely finished for at least 2 years.

Here is what they said:

On 02/08/2008 you, or the designated representative shown below, contacted us about your case.

The status of this service request is:

On 3/12/08, we created an Advance Parole document for you and mailed it to the address we had on file at that time. You have notified us that you have not received it and the post office has not returned it to us. We must conclude that it has been lost in the mail. Therefore, you will need to file a Form I-131, Application for Travel Document with fee. You can download this form on our website www.uscis.gov. You can also file this form electronically on our website. Please follow the instructions on the form.

SO WEIRD!!! Well, I received the AP for nearly 3 months already now. Or if it's really lost in mail?? It's not my fault - why I need to apply again WITH FEE????

I can "comiserate" with you about INS/USCIS incompetence (except that the delay then didn't really cause me any misery).

I had proceeded to Montreal in Dec 1999 for my GC interview on a "pending" TN-1 renewal, with original TN-1 about to expire (had I not had the GC interview, it wouldn't have been a good idea to travel, as INS would consider the I-129 petition as abandoned). I was approved at the interview and activated the Immigrant Visa at Dorval's PFI later that day, returning to Atlanta in the evening.

Eight weeks after the interview, I received my plastic GC. But the topper was that I got an approval of the TN-1 extension two weeks after that--when I no longer needed it at all!

You don't need to apply again. The AP is only useful before you have your green card. Now you have your green card an AP has no use or value for you. This is just a system that is so slow and so backed up that you should have received this response shortly after you inquired about your missing AP rather than 4 months later. And, since you received the AP, it is no longer missing. This is a message that you can safely ignore.

Maybe they are playing games?

Doesn't seem so but USCIS actually does pretty good processing over 7 million visas a year!!
Not sure about how many but it's a LOT!

A little complex, as they "delegate" issuance of most of them (some exceptions such as TN-1's, L1-A/B specifically to Canadians) to State Dept.