Sony Xperia Z1 randomly rebooted and when it came back up, apps on the SD card read "Application not found" Just last night I was moving apps to my SD card and the phone (Sony Xperia Z1) randomly restarted. When it came back up, all the apps on my SD card no longer worked. Their icons became generic with a tiny SD card in the bottom corner. 

When I tap an app, I get the message "Application not found". I've tried un-mounting and removing the SD card, restarting, clearing cache, but nothing works. 

When I go to the App Store, the apps show up as if they need to be installed but when I look at the SD card via my PC, all the files are there still. The pictures and videos are still accessible from the phone however. Before that, I had problems moving a game to the SD card. I kept getting a "Not enough memory" error, even though all the other movable apps moved and I deleted apps to make space. 

I tried options I found on the forums and other websites but to no avail, and the only thing I haven't done yet is to root my phone, which I am trying to avoid.
Maybe I can help with part of your question.  I too have had a 'Not Enough Space' issue.  I deleted a bunch of files and off-loaded more, still I could not move or edit other files.  Going to settings and checking 'Device' 'Storage' the operating system indicated that I had over 2/3 of my internal memory available. 

I found that if I power cycled the device it would reset the file space available counter in another part of the operating system.  I also found that I could not count on my deletions or moves being deleted or moved unless I used the Power Cycle trick very soon after preforming the deletions or moves.