I really don't think that caching should effect the messages at all. I wish I could give solid advice on this, but having never had to do anything with product-level messages, I'm just throwing some ideas out there.
I don't believe that product-level messages behave in the same way as the session messages you see when you get to the cart. I'm not exactly sure how the product view picks up messages, but it might be more done on the layout level. I was digging around a bit, and perhaps one thing you could try is something like this:
Mage::getSingleton('core/message')->notice($message)
If that fails, dig through app/code/core/Mage/Catalog/ and see if you can find examples of how Magento sets messages to be picked up on the product view.
I hope you find the answer!