ragnawing: The videoes are definitely encoded in 16:9 aspect ratio, but by default, the game's code has videos set to run at the original aspect ratio of 4:3. Apparently, XSEED couldn't or didn't change the aspect ratio limit on the videos.
SirPrimalform: It's not 4:3, it's something between 4:3 and 16:9.
I opened the videos directly in a tool called MediaInfo. It shows the exact data of how any video is encoded. Here is the data for the opening video:
General
Complete name : C:\GOG Games\The Legend of Heroes Trails in the Sky\ed6_op.avi
Format : MPEG-PS
File size : 103 MiB
Duration : 3mn 20s
Overall bit rate mode : Variable
Overall bit rate : 4 314 Kbps
Writing library : encoded by TMPGEnc (ver. 2.524.63.181)
Video
ID : 224 (0xE0)
Format : MPEG Video
Format version : Version 1
Format settings, BVOP : Yes
Format settings, Matrix : Custom
Format settings, GOP : M=3, N=18
Duration : 3mn 20s
Bit rate mode : Variable
Bit rate : 3 972 Kbps
Width : 1 280 pixels
Height : 720 pixels
Display aspect ratio : 16:9
Frame rate : 30.000 fps
Color space : YUV
Chroma subsampling : 4:2:0
Bit depth : 8 bits
Scan type : Progressive
Compression mode : Lossy
Bits/(Pixel*Frame) : 0.144
Time code of first frame : 00:00:00:00
Time code source : Group of pictures header
GOP, Open/Closed : Open
GOP, Open/Closed of first f : Closed
Stream size : 94.8 MiB (92%)
Writing library : TMPGEnc 2.524.63.181
Audio
ID : 192 (0xC0)
Format : MPEG Audio
Format version : Version 1
Format profile : Layer 2
Duration : 3mn 20s
Bit rate mode : Constant
Bit rate : 256 Kbps
Channel(s) : 2 channels
Sampling rate : 44.1 KHz
Compression mode : Lossy
Stream size : 6.11 MiB (6%)
The videos are literally encoded to a 16:9 aspect ratio at exactly 720p. The game engine is probably what restricts it in-game to make it look the way it does.