The same way you would check whether or not you needed to generate the random number for duplicate titles in the first case. Make it a function, 'check_duplicate()' and run it once to see if the number needs to be generated, and again to make sure the generated number isn't already in there.

Or take a page from WordPress and generate it in numerical order. Find the last title, 'some-duplicate-title-2' and add 1 to it.