How can I clean up 'Other' storage on iPhone 3G?
I had this same exact problem until 2 days ago followed the procedure outlined on this page: http://www.ipodrepublic.com/iphone/fixing-issue-other-files-iphone-memory/2010/03/31/ and it worked well.  Re-created below.  I haven't seen my Other size grow since.

Step 1: Turn of sync music in iTunes

When you have synced your iPhone and noticed that “other files” have taken up a lot of storage space on the iPhone, un-tick the “sync music” alternative in iTunes before un-connecting your iPhone.

Step 2: Install DiskAid software on computer/mac  (Instead of using DiskAid (paid), I used iPhone Explorer (which is free.))

DiskAid is a neat little software that allows you transfer files to your iPhone, iPod Touch, or iPad, treating it as a USB drive. They offer a free trial of the software so no need to purchase it first time you have to use it at least.

Make sure your iPhone is connected with the USB when you open up DiskAid. When the program is running, at the bottom left corner it says “DiskAid folder”, click on the drop down list and choose “media folders”.

Step 3: Go into iTunes Control folder and then the Music folder

In DiskAid you will see an overview of all the folders and files on your iPhone. Go to the iTunes Control Folder and then the subfolder called Music. Under the Music folder you will likely see a lot of subfolders starting with “f”.

Step 4: Delete/remove all subfolders in Music

Delete all the subfolders under the Music folder. They include the files that are hogging your iPhone memory under “other files”.

Step 5: Open iTunes and sync your iPhone

With “music sync” still turned off in iTunes, sync your iPhone. This will remove all music files from your iPhone, but keep all other content. Don’t worry about this though, as in the next steps you will sync the music back onto your iPhone.

Step 6: Unplug iPhone and reboot it

Once the iPhone has finished syncing, unplug it and perform a reboot. The reboot is done by holding down the “power down” button at the top right at the same times as holding down the control button. Hold both of them until the iPhone has switched off and the Apple logo appears on the screen before releasing both buttons. This action will reboot your iPhone.

Step 7: Reconnect your iPhone to iTunes and recheck “sync music”

This will put your music back onto the iPhone, and you should not see any of the “other files” taking up any of the iPhone memory. Once the sync is complete your iPhone should be all sorted again.

If you still see “other files” taking up memory on your iPhone you have likely done something wrong or left out subfolders in step 4.

Also, delete the same type of sub-folders in the PWNTunes Itunes Control folder as well if you are jailbroken and have PWNTunes installed.