I believe adding more controls will help the user to quickly move over that huge list..
Additional controls may include:
- Autocomplete field.
- Categorized or Paged list based on whatever criteria (Numbers, Letters, ) .
- Showing Multi-Column list instead of regular 1 column one (see the last image).
- Ability to pin/unpin the list , so that user don't lose the list when accidentally click out of it.
Checkboxes are fine, But highlighting the selected value and showing them in an additional result column is better!
Just make sure that the user will be easily able to reach and pick any item from the list. And remember to make simple as well.
One last thing, Make a usability testing on that case -although it might be expensive sometimes!- specially if that feature is a key one in your app.
some examples :

