124 characters, with the following features:
- Digits are displayed on a single line instead of scrolling the screen. (Tested only on Linux with bash.)
- Execution takes anything between $D and $D*10 seconds to run, when using base 10. Thus, if $D == 10, the program may run for as long as 100 seconds or 1 m 40 s. $D == 15 will break the "bonus barrier".
perl -e'$|++;split//,int rand 10**pop;sub f{$.=++$.%10;print$.;sleep 1
+,print"\b";$.==$_[0]||&f;print
shift;@_&& &f}&f;print"\n"' 10
You may additionally add ."\a" after print shift to produce a bell sound after a digit has been successfully found. That increases character count to 129.
The OP is ambiguous, though. It says pick a number between 0 and 1e$D-1, but doesn't say whether it should contain prefix zeroes or not. My code doesn't produce prefix zeroes.