For what it's worth, the next version of Regexp::Assemble (v0.24) will be able to do the following

$ perl -le 'print $_ for 4333 .. 9999' | \PERL5LIB=blib/lib assemble
(?:4(?:3(?:3[3456789]|[456789]\d)|[456789]\d\d)|[56789]\d\d\d)
[download]

... in 1.3 seconds on hardware a couple of years old.

If I get the warnings to stop, I'll throw in japhy's mind-bendingly marvellous list-to-range regexp which will allow it to get that down to:

(?:4(?:3(?:3[3-9]|[4-9]\d)|[4-9]\d\d)|[5-9]\d\d\d)

... which, interestingly enough, looks as if it arrives at the same conclusion as you, which is a nice validation, thanks :)