Index: rhythmdb/rhythmdb.c
===================================================================
--- rhythmdb/rhythmdb.c	(revision 4985)
+++ rhythmdb/rhythmdb.c	(working copy)
@@ -3147,6 +3147,29 @@
 			gnome_vfs_result_to_string (res));
 }
 
+static gboolean
+confirm_unlink (GnomeVFSURI *uri)
+{
+    GtkWidget *dialog;
+    int response;
+
+    dialog = gtk_message_dialog_new (NULL,
+                                     GTK_DIALOG_DESTROY_WITH_PARENT,
+                                     GTK_MESSAGE_ERROR,
+                                     GTK_BUTTONS_YES_NO,
+                                     "Cannot move file to trash, do you want "
+                                     "to delete immediately?");
+    gtk_message_dialog_format_secondary_text (GTK_MESSAGE_DIALOG (dialog),
+                                              "The file \"%s\" cannot be "
+                                              "moved to the trash.",
+                                              gnome_vfs_uri_to_string (uri, 0));
+    gtk_window_set_title (GTK_WINDOW (dialog), "");
+    response = gtk_dialog_run (GTK_DIALOG (dialog));
+    gtk_widget_destroy (dialog);
+
+    return response == GTK_RESPONSE_YES;
+}
+
 void
 rhythmdb_entry_move_to_trash (RhythmDB *db,
 			      RhythmDBEntry *entry)
@@ -3164,14 +3187,29 @@
 	res = gnome_vfs_find_directory (uri,
 					GNOME_VFS_DIRECTORY_KIND_TRASH,
 					&trash,
-					TRUE, TRUE,
+					FALSE, TRUE,
 					0);
+
+        if (res == GNOME_VFS_ERROR_NOT_SUPPORTED) {
+                /* Didn't find trash, try to create */
+                res = gnome_vfs_find_directory (uri,
+                                                GNOME_VFS_DIRECTORY_KIND_TRASH,
+                                                &trash,
+                                                TRUE, FALSE,
+                                                0);
+        }
+
 	if (res != GNOME_VFS_OK || trash == NULL) {
-		/* If the file doesn't exist, or trash isn't support,
-		 * remove it from the db */
-		if (res == GNOME_VFS_ERROR_NOT_FOUND ||
-		    res == GNOME_VFS_ERROR_NOT_SUPPORTED) {
-			rhythmdb_entry_set_visibility (db, entry, FALSE);
+		if (res == GNOME_VFS_ERROR_NOT_FOUND) {
+                        /* If the file doesn't exist, remove it from the db */
+                        rhythmdb_entry_set_visibility (db, entry, FALSE);
+                } else if (res == GNOME_VFS_ERROR_NOT_SUPPORTED) {
+                        /* If trash isn't supported, ask if it should be
+                         * deleted immediately */
+                        if (confirm_unlink(uri)) {
+                                rhythmdb_entry_set_visibility (db, entry, FALSE);
+                                gnome_vfs_unlink_from_uri (uri);
+                        }
 		} else {
 			rhythmdb_entry_move_to_trash_set_error (db, entry, -1);
 		}
