I'm wondering what is the use of the wp_links table, couldn't links have been implemented as a custom post type, if the menu system also uses custom post types?
In short YES, they could have. As anything else could have been implemented as custom post type and/or custom taxonomy.
But WordPress is a grown system - now 9 years old - and things are moving slowly to keep most stuff backwards compatible.
In short, with WP 3.5, the Links Manager will be moved to a plugin, as you can read in the trac ticket.