Do you have Microsoft Outlook on your MacBook Air?
Recently, I constantly got "Startup Disk is full" even when I removed some large files. After I checked all my photos, music and movies, I started to suspect Microsoft Outlook, for I had problems with it in the beginning. I tried to find Outlook file directory of Outlook and could not find the directory nor my personal mail file (pst files). So I played around and went to Tools\Run Schedule\Empty Deleted Items Folder, and tried to permanently delete all deleted messages. I was a little concerned when it took about 10 minutes to complete, and has obviously cleaned up multiple folders.
When it's done, I have emptied trash can and shutdown my MacBook Air (Yosemite). When restarted, I was so pleased I got 28GB of my 128GB system Disk storage back.