I have just installed the plugin on Joomla 2.5 for the first time and have made no parameter changes.

My MP4 file is in images/stories/videos and the joomla article has the following in it: {mp4}MyTalkingPet{/mp4}

The file plays fine on my PC with Windows Media Player. Do I have to have it in a sub-folder? It didn't appear so. I have no idea what's wrong and have looked at the other forum entries for this same error message.

I think I've sorted it.

What was the issue?
Was your path correctly setup in the plugin's settings?

The path was set wrongly in the plugin video section. However, I am having various browser-specific problems. It works fine in Chrome. In FF the sound is fine but the flashblock icon appears and I can't OK the video as clicking on it stops the sound. In IE it just doesn't work at all.

Furthermore, I installed this so I could include a video link in a newsletter (AcyMailing) but I'm now doubtful if that would work. What's your advice?

I do not know if AcyMailing parses content plugins in their newsletter.
This is something that the AcyMailing devs know.
However the video most likely will never display in the newsletter. I think that videos are not support by most email providers/ clients.

As for crossbrowser issues you can check your codec's compatibility here: caniuse.com