Try your best to find the address and phone number - ask friends and family, someone might remember. If you can't find them, just write a brief explanation and as many details as you do remember.
For what would be considered 'strange' addresses, just write a description of where you lived. The examples given in the posts above would be acceptable. For the address section, CIC wants to know where you actually lived, so if the mailing address was a PO box, include an explanation and the address/description of your residential address. I would put both the Spanish (or whatever language) and the English translation.
In my application, I had to attach a separate sheet of paper with an explanation of 1. that I didn't know the phone number and street address of a couple of places I lived, and 2. a description of where I lived when that place had no real street address. For example: "From February 2, 2004, until January 31, 2005, I lived on the campus of the .... University in Mianyang, Sichuan, China. There was no address. My apartment was in one of the two apartment buildings reserved for senior staff and foreign teachers at the top of the hill on campus. My apartment was the one on the left on the ground floor of the first building up the hill."
OK, so if they really want to check this, they could find it.