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.