How taxed is your server when you're generating the cache? Is CPU and RAM maxed out or is the server still generally healthy? How's your disk space; is there enough storage capacity for the anticipated tiles?
When you say that sometimes it works and sometimes it doesn't, for the times where it doesn't work are you certain that the previous attempt to create the cache tiles has been completely terminated? There may still be ArcSOC processes running on your machine that have not been released properly, thus preventing subsequent cache processes to never complete or start properly. Between cache creation attempts, try restarting the ArcGIS Server service or SOM first.
