After having struggled with this issue for several days - and finding a solution - I thought I'd share this with you all.

The issue I was having was when an image was inserted into a node, it would be visible while I was logged in. However, anonymous users couldn't see the image, even though the path seemed correct.

I was using img_assist and IMCE to do the insertion and both had the same problem. Hence, not a problem with either of them.

I was using the private file system so that the file paths would always be something like /system/files/image/image.jpg. Since I was on a multi-site Drupal install, this was much cleaner than the actual full path. This is also a great way to avoid site migration issues with your files folder when moving from a regular local install to a multi-site host setup.

I made sure that the files folder was correctly referenced too, which it was. However, I was still not seeing the images. I even changed the owner of the files to root to see if that did something. Nothing.

Drupal forums were kinda vague on this whole thing, but two posts pointed me in the right direction. The first one mentioned the fact that the upload module should be enabled, as the image upload hooks into it. Checked it, and it was already enabled. The second post mentioned something about access control and the upload module, so I checked that and there was the solution!

Enable view uploaded files for all your users and voila! All images are now visible to anonymous users (as well as registered users too).

Oh, and you might want to try emptying your cache if things don't appear to work as described here. Thanks to Max for this tip