Today I had this strange problem: deleting files without gaining free space and having it decreasing with no sense. I started investigating what the hell was going on on my Macbook Air and, after half an hour of investigation, I figured it out: Time Local Snapshots!
I have my Macbook Air with Time Machine connected to an Ubuntu 10.04 server ‘faking’ a Time Capsule, thank to Netatalk, and I discovered that Mac OS X starting from Lion, has the local snapshot enabled as default on notebook.
This means that a local copy of files are keeped in the local drive, using space. So, if you want to check how much space are the snapshots using, you just have to open the terminal and run:
sudo du -sh /.MobileBackups
This was on my machine:

From my point of view this is a waste of space so I decided to turn off this feature. The command to do this is quite simple (always using the Terminal):
sudo tmutil disablelocal
Immediately after this command, Time Machine should start a backup indexing all files from scratch and deleting the /.MobileBackups folder.
P.S. Please be careful in doing this, I’m not responsible to any data loss or damages