for clouds weapons you might look into Aurons Weapons for some inspiration as well as some of the weapons in FFXII
Cid - Also FFXII has some lance type weapons too
Vincent - FFXI has some gun type weapons, also FFX2 has some gun weapons as well, Dirge of Cerberus as well
(I'm starting to think about what monsters could be put in for his transformations, I know his flame and chaos forms are on Dirge of Cerberus, don't know about others)
Tifa - at the moment I'm thinking FFXI might be the only newer game to be able to get High res weapons
Cait Sith and Red XIII might be a lost cause lol or custom onlys
Yuffie - Her kingdom hearts weapons
Aeries (too tired to remember spelling...) - FFXII has some staff weappons, FFX & FFX2 do
Barrett - I suppose you could just cut off the handle of other large guns and strap it to his arm (lol)
(I haven't played FFXI so I have no clue about its weapons)
Also here is a weapon from XI I just found a screenshot of that looks very similar to one you guys were playing with
http://www.playonline.com/ff11us/ahturhgan/equipment/algol.html