Well, indeed, Intelligence and Luck are most important attributes. However, the natural 100 aren't quite enough to be sure in success for most complicated enchantments even if one's Enchant skill is also 100. It's because i always start with some Alchemy to boost the attributes far over the natural limits. Surprisingly, but the Personality is one more attribute you'd wish to boost before you're going on to something really serious. It's not my discovery, i got it from some post on this board (if only Gamebansee's search might work a bit better!), but i've got quite sound confirmation on it in my experience. As soon you can get 4000+ Intelligence, 1000+ Luck and about 1000 Personality the probability of failure is fairy low even if your Enchant skill is bellow 50.
Also i have discovered for me that the best way to develop Enchant skill itself is recharging instead of enchanting, moreover the size of a gem does not matter that much in this case and there's plenty of cliff racers in the game. And, as soon as you're going to use enchanted items you're interested in possibly higher Enchant skill even if you're a plain warrior - there's a difference if your enchanted sword gets exhausted after 20 or 60 blows, isn't it?
BTW, to start to develop the Enchant skill helps a little item i've used for quite a few games by now. It's a common ring absorbing 1 pt fatique on self for 1 sec

It does no harm because it's exactly the natural fatique restoration rate.

The other, more useful is also common ring restoring some amount (max. for Common ring, in fact) of fatique at once - very worthwhile at long running, esp. if an unexpected encounter happens

They both are very cheap to buy at any professional enchanter altogether.