Before attempting anything below, make sure you have a working backup of your complete site, just in case.
FILES:
First check for any files in your Joomla installation. Using FTP look at and remove the whole folders (if found) in the following locations:
- administrator/components/com_weblinks
- components/com_weblinks
- modules/mod_weblinks
- plugins/search/weblinks
- plugins/finder/weblinks
DATABASE:
Then with a database tool, like PHPmyAdmin, connect to your database and look at the following tables:
#__extensions
look for any rows where name LIKE '%weblinks%' and delete them. This will delete all references of the package/component/module/plugins of the weblinks.
#__categories
look for any rows where extension = 'com_weblinks' and delete them. This will clear your categories table from any weblinks categories.
#__assets
look for any rows where name LIKE '%com_weblinks%' and delete them.
This will delete the asset for the component itself and also any possible categories of the weblinks component, that still have an asset in the assets table.
#__menu
look for any rows where path LIKE 'Weblinks%' and delete them. This will delete any references to the component in the admin menu.
#__weblinks
Delete the whole table.
I think I have included everything... as said at the top of my answer have a tested backup, in case something goes wrong while you are deleting folders and data in your database.
You might be also better if you try all these at a testing site.
