Here's a thing to check your Banshee library for files that are no longer present. It tells you which ones it will remove first and asks you if you want to. It's only removing the database entry.

reap-dead-tracks.pl

#!/usr/bin/perl

# adapted from https://gist.github.com/bitfolk/6856343
# License: None(none specified in original code)
#
# Usage:
# - install Perl DBI modules:
# - (libdbi-perl, libdbd-sqlite3-perl for ubuntu)
# - Run reap-dead-tracks.pl <database>

use warnings;
use strict;

use DBI;
use URI::Escape;
use Term::UI;
use Term::ReadLine;

my $dbfile = $ARGV[0];

# Default location of library if not specified.
# Do not work on a live db, and do backups.
# Banshee db is in ~/.config/banshee-1/banshee.db by default
$dbfile ||= $ENV{HOME} .'/Downloads/banshee.db';

if (! -e $dbfile) {
	die "Banshee library $dbfile doesn't exist";
}

if (! -r $dbfile) {
	die "Can't read Banshee library file $dbfile: $!";
}

print STDERR "# Connecting to $dbfile ...\n";

my $dbh = DBI->connect(
	'dbi:SQLite:dbname='. $dbfile,
	'',
	'',
	{ RaiseError => 1 },
) or die DBI::errstr;

my ($sth, $row);

$sth = $dbh->prepare(qq{
SELECT TrackID, Uri
FROM CoreTracks
});

$sth->execute;

my @missing;

while ($row = $sth->fetchrow_hashref) {
	my $id = inspect($row);
	push(@missing, $id) if (defined $id);
}

print STDERR "# Done!\n";

if (0 == scalar @missing) {
	print "All tracks present.\n";
	exit 0;
}

my $term = Term::ReadLine->new($0);
my $bool = $term->ask_yn(
	prompt  => 'Remove these '. scalar @missing
			.' tracks from Banshee library?',
	default => 'n',
);

my $del_count = 0;

if ($bool) {
	# Expand list of track IDs into SQL query IN (1,4,5,...). Can't work
	# out how to do it with parameterization, or even if you can.
	my $sql = 'DELETE FROM CoreTracks WHERE TrackId IN ('. join(",", map { $dbh->quote($_) } @missing) .')';
	$sth = $dbh->prepare($sql);
	$sth->execute or die $sth->errstr;
	$del_count = $sth->rows;
}

$dbh->disconnect;

print "$del_count tracks deleted from Banshee library $dbfile\n";

exit 0;

sub inspect
{
	my ($row) = @_;

	die "Expected a DBI row" unless (defined $row);

	my $id  = $row->{TrackID};
	my $uri = uri_unescape($row->{Uri});

    # catch mtp connections as well
	if ($uri !~ m#^file://|^mtp://#) {
		printf STDERR "Skipping non-file URI: [%d] %s\n", $id,
			$row->{Uri};
		return undef;
	}

	$uri =~ s#^file://##;

	if (! -e $uri) {
		printf "Missing: [%d] %s\n", $id, $uri;
		return $id;
	}

	return undef;
}