It's normal for PSX games to show small vertical bars on the sides even in Full Screen setting. It varies from game to game, because of the original resolution of some of these games. Some games had better resolution than others.
I would caution those playing with the multiMAN settings and putting their resolutions for PSX games to PAL (576 is PAL) which can cause issues on NTSC TVs. I personally feel that you should just leave those PSX muiltiMAN settings to default. You might end up with a game that may not work, and you will forget that those settings you set may be causing the issue.
PSX Native resolution
Games are always 4:3 with any resolution between 640x480 NTSC / 640x512 PAL (the bios initialisation screen) and lower:
Horizontal: 256 (rare e.g. Dragon Warrior VII), 320, 368 (occasionally 384 e.g. SF Zero 3 but not X-Men vs SF which was shrunk to 368), 512 or 640
Vertical: 240 (NTSC), 256 (PAL), 480 (NTSC), 512 (PAL)
Tekken 3 uses a strange pixel area of 368x480. Regardless of the screen area, the aspect ratio is still 4:3 for all PlayStation games. Very common resolutions : 320x240 for NTSC and 320x256 for PAL.