only with fedex. you have to ask when you call them. if they tell you they cant, it might be due to canada, but i tell you i do it aLL THE TIME here in the U.S.
i call, i give them my exact address, tell them i am concerned i might be being frauded and cannot get a tracking number, and they look it up, and will even be able to tell you the name of the sender etc if it is in their system.
ONCE i got UPS to do the same thing, but recently every time ive called they said they cant do it. so either i got lucky once with somone who knew wtf they were doing or they changed software or something.