Sounds like good times.
Also you're forgetting about VF5:R, which was released in between 5 and FS, which is why the wait seemed so long. And the fact that Sega waited for PS3 was understandable for 5 Vanilla, but there wasn't so much excuse for such a long wait for the later iterations.
I understand them not wanting to ruin their Arcade income by making a fast console port, but still, it got a LOT of backlash from VF fans at the time. I wish I coudl find the video of a guy putting his copy of VF5 through a paper shredder in blind range.