I think you'll find a topic with what cards to lose to the Queen of Cards, where you can get the new one and and find the old ones
just search a bit ..
But I found this little trick that I wanted to share ..

It's easier if you start it at Disc 3 when you have the Ragnarok
When you start the Queen of Cards Quest, you loose a LV8+ card to her (not 1 of the 5 you'll need, so don't lose Minimog)
so perhaps when you start with that quest you'll lose Angelo or so to her
This is easily done with the Direct Rule ..
Ok, now she moves to another location .. you know that ..
Go there and lose another card (hey no difference, just wait)
you could have won back your old card, but for now just loose another one to her.
She'll move again etc, keep losing LV8+ cards, so when she arrives in Dollet, she has at LEAST 4 or 5 cards of yours
Go card to her and Quit until you get the Direct rule .. (you'll need some card skills too)
If you get lucky, you will use MiniMog (or the card she asked you) and she will use one of your LV8+ cards.
If so, get that LV8+ card of yours and give her the MiniMog in 1 game with the Direct Rule
That way the game doesn't see neither a loss nor a win of a LV8+ card ..
Now the Queen stays in Dollet .. You can go and get the new card, get your old card, and then repeat it with the next card she asks (4rd option when you talk to her)
If she doesn't use a LV8+ card, of you haven't got the card she asks, just don't lose or win a LV8+ card and try it again

Can someone confirm this ? With me it worked fine ...
It saves you a lot of hunting for the queen :)

EDIT : copied this from a site :
Card Given/Card Created/Where to find New Card
MiniMog :: Kiros is created: Found in Deling City by the man in black across from Junk Shop.
Sacred :: Irvine is created, find in FH; win from Flo (Mayor Dobe's wife).
Chicobo :: Chubby Chocobo is created; win in Balamb Garden from student sitting on bench outside library.
Alexander :: Doomtrain is created; win in Timber from the Pub's owner.
Doomtrain :: Phoenix is created; win in Esthar from the blue Presidential Assistant in the Presidential Palace.

Or you could wait till disk 4 and go 2 the escape pod site 2 get all the cards alternatively do the cc member in balamb garden and verse the cc members in ragnarok to obtain all the cards also you can refine and win back the cards over and over.

I did that too, believe me, but you don't have a lot of pleasure with Accelerators for example on Disc 4 when you have to fight Ultima Weapon on Disc 3 if you know what I mean .. So it might be better to get some of the items early and then it's kind of a useful trick