IT office; a lot of time voicemail accounts get set up but people don't necessarily check them. Personally, I prefer speaking directly to someone or having a paper message left rather than leaving a voicemail which may or may not be checked and may or may not be returned. But also, I know how offices work and are laid out, and that the person taking the calls may not be anywhere near the person I want to reach, and they can't just "duck over" to their desk and leave a message, even if they could leave their duties.

In this situation, I would probably give them an email address instead, and let them know that that's the alternative.

Or I'd probably be polite and blunt if they persist:

"I'm afraid I'm not X's personal assistant, so I don't know where they are." And if they pester to leave a message, I'd tell them "I can take a message but it will sit on my desk (in this other division) until they come to pick it up, because I have my own set of tasks to complete and it doesn't include playing messenger girl. They come past once every couple of weeks and I am not always here when they do. As a result, I cannot guarantee that they will receive it in a timely manner. Your best option is to leave a voice mail or email them."

I think people have outdated ideas of how offices are set up (particularly in larger corporations with multiple divisions) and think that The Person Who Answers The Phone is actually the general dogsbody for the office.