Since not all videos fail I'm posting some additional information:
This video does not play:
$ ffmpeg -i bbctstory00.wmv
...
Input #0, asf, from 'bbctstory00.wmv':
Metadata:
WMFSDKNeeded : 0.0.0.0000
DeviceConformanceTemplate: MP
WMFSDKVersion : 12.0.7601.17514
IsVBR : 0
Duration: 00:05:10.10, start: 0.000000, bitrate: 7175 kb/s
Stream #0:0(jpn): Audio: wmav2 (a[1][0][0] / 0x0161), 48000 Hz, 2 channels, fltp, 192 kb/s
Stream #0:1(jpn): Video: wmv3 (Main) (WMV3 / 0x33564D57), yuv420p, 1280x768, 8000 kb/s, 60 fps, 60 tbr, 1k tbn
This video plays:
$ ffmpeg -i bb15story00.wmv
...
Input #0, asf, from 'bb15story00.wmv':
Metadata:
WMFSDKNeeded : 0.0.0.0000
DeviceConformanceTemplate: MP@HL
NumberOfFrames : 1322
WMFSDKVersion : 11.0.5721.5265
IsVBR : 0
Duration: 00:00:22.52, start: 0.000000, bitrate: 6148 kb/s
Stream #0:0: Audio: wmav2 (a[1][0][0] / 0x0161), 48000 Hz, 2 channels, fltp, 192 kb/s
Stream #0:1: Video: wmv3 (Main) (WMV3 / 0x33564D57), yuv420p, 1280x720, 8000 kb/s, SAR 1:1 DAR 16:9, 60 fps, 60 tbr, 1k tbn
The resolution is different, but the opening is also 1280x768 and that video works. I'll post which videos work and which don't when I finish the game.
Nothing extracted yet.
Compatibility Report
System Information
I confirm:
steam-294810.log
Symptoms
Videos in story mode don't play, only the intro.
Reproduction
There are two ways:
Here is what happens:

Debug
What I found so far:
data/Movieof the installation directory.wmav2and the video codec iswmv3for all videos, so gstreamer needs the libav plugin.compatdata/294810/gstreamer-1.0.