I have a USB stick, which I store files on. The disk tends to "lose" space, which means that when I delete files, the size of the deleted files doesn't get freed up.

Example:
Space on disk 128mb
I copy files which is 10 mb to usbdisk, leaving 118 mb on disk, then deleting them
Then the disk is still 118mb

So I need to do this in order to restore the usb stick to its original capacity:
mkfs.vfat /dev/sdb1

However, this is not very convenient, because then I have to move all the files, temporarily, to another location, and then copy them back. Is it because of inconsistenties in the file system this tends to happen? How can I solve this without formating?

My file system is vfat, because I need to use the stick on MS Windows and Linux.

I've had this trouble once or twice myself... when it happens I have to re-format the stick too.

I've had the best result by copying files, then deleting the ones on the stick, when I have to move files.

Tell me, do you use the gui for these operations or the terminal?
If you normally sue one, try the other just to see. Normally the file is not erased from the media, just the filename from the file allocation table. So the space will not look vacant (all zeros) to some software/hardware combinations. It sounds as if something is removing the filename but not resetting the empty-space pointers... hmmmm.

Let us know, step-by-step what you are doing...

1. write to media: ie
[bash]$cp testfile /mnt/m-stick

2. erase from media: ie
[bash]$rm /mnt/m-stick/testfile

check the memory before and after each step. you may want a look at the system logs too... funny errors can show up there.
if the problem persists... past everything here.