I just left a message for a coworker on his voice mail for his mobile phone. I could barely understand his message, as it sounded as if he recorded it while driving in the car. It reminded me of how much I find it annoying when I hear something like that.
Voice Mail messages, whether for mobile or the office, one should always do it when there isn't any background noise. It's just basic professionalism.