We have a phone that has the intercom button, of course, and 2 pivate lines on buttons. The way a greeting is tied to the phone is to do a #656 at the phone to tell vm what is going where. To turn the message light on, the #657 is done. On these two lines, which are CO lines directed to that phone with prog 81 and *81, the previous owners message still shows. We are using Phone Express Vm. Is it possible that the private lines recording is at the Phone CO, since there is not a port tied to them?

Very possible. Disconnect the voicemail on site and call the lines. If a message answers you know its at the CO.