Don't listen to the 'It is random and keep trying' answer. It is far from random and predictable and/or repeatable. I think I'm going to write a FAQ for it, but as Im a bit nonchalant about it, it may take me some time. This should actually work for any rule change, not just removing random from dollet (I actually removed both elemental and random - once I figured out the pattern, I got both removed within about 10 minutes). Before moving on, I want to note that I am using an original PSX version of the game playing from a PS3.
To do this...
Save your game at one of the save points in Dollet (I used the one in the place where the card queen appears). Before you do anything, see if anyone there will change the rule giving you the result you're trying to achieve (probably not). Anyway, once you fail to get what you want, reset and try that same person again (you will get a different result this time). Now you might be saying 'what's your point - this is random'. I can say 'wrong, it's not'. Try resetting your game and trying again (always use soft reset from the XMB menu on ps3), you can use any person and the result will be the same (do not change screens). Not only the result but the number of times needed to talk to the person to change the rule will not change between resets. How do we use this you ask? I am glad you asked!
The random number seed that everyone talks about? Yeah, it changes every time you move from screen to screen in FFVIII. All that you need to do is make the screen change to get a different result. If you track how many screen changes you used and the resulting rule change, you can actually duplicate the result every time regardless of who you play cards with (when I did it, elem abolishment was on the sixth screen (b/c of where I saved it, it was not possible to get 3 or 4 screens which is where I think random would have been abolished and probably why this is such a pain to get through dumb luck). Always count the place where you saved as screen 1 moving to the next area would be screen 2 and so on. Coincidentally it was exactly 6 screens for me to get to the dollet hotel and play the girl in there, starting from the queen of cards location. You can play anyone without affecting the results in any way. I believe the 'base start seed' (for lack of a better term) is preserved in some way when you save. I speculate that square did this INTENTIONALLY so you CANNOT just reset the game and get a different result. Lots of turn based games do this (Civilization IV for example even gives you the option to turn it off).
As a note, I would recommend starting this in the dollet hotel because there is someone in the room who plays and someone outside. Going outside and back inside will let you hit every number of screens possible (allowing you any result you want). Also note that there is a pattern to the rule changes and you will notice as your number of screens gradually increases, you tend to get the same result (either that or it then becomes required to go thru exponentially more screens to get a different result, I stopped getting different results after screen 10, and I went all the way up to about 30). Anyway, I really doubt you will need that many, unless you want to do some math to figure out how this actually works. I stopped caring after random was abolished.
I guess I will write a FAQ eventually, but you can e-mail me gmail if you really need more information or dont understand this. It is as simple as it sounds though...