I have a workaround for this... it's a bit messy, but it works. You need to have phpMyAdmin access for the database. And obviously all the usual "OMG, don't do that" warnings apply - take backups, don't blame me if it fails, etc. :)
I just got rid of over 200,000 unattached media items on one of my blogs by this method.
1. Install the DX Delete Attached Media plugin (http://wordpress.org/plugins/dx-delete-attached-media/)
2. Create a new post. I named mine "Unattached media" and saved it as draft.
3. Find the post number. Just go to the posts list, click the post title and look at the URL: it will have "post=xxxxx" in it.
3. Run the SQL in your phpMyAdmin interface:
SET post_parent = [post number of your new post]
WHERE post_type = 'attachment'
AND post_parent = 0
4. Go back to your posts list and send your post to the trash.
5. Make sure the DX plugin is activated, empty trash. Bingo, all dead items gone.
Note that if there are a LOT of items, you might have to just leave the post in the trash and wait for WP's standard trash emptying procedures to handle it. But it still works.
Hope it helps!