Custom taxonomy should be ruled out if venue needs to hold lots of information.
Which leaves you with custom post type or custom DB table, so:
Custom DB table would be the best option in performance point of view since it will only holds the needed fields and not all of the CPT fields (from the WP_posts table) and it will allow you to query a single database table instead of 2 (post meta).
But creating a custom table you loose all of the native functionality like admin UI, WP_Query … which you will have to custom code from scratch.
Now using a custom post type you can simply create a venue custom post type which will use the native admin UI and all Query functions you need. Add a few post meta fields (address and stuff).
and all that is left for you to do is create a meta-box in the event CTP edit panel to select a venue for a list.
I would probably go with Custom post type.