Free promotional CDs definately work,
been doing a local artists compilation down in Portsmouth, just had a release party for the 2nd one, which was a double CD affair, the first more electronica and the second more techno based.

We gave em away to the first 100 through the door and the response was great, primarily from the people that had got a copy of our first one at clubs and pubs around here.

We incorporate the website address into the artwork, so the people that get the CD can spread the word, as all the tracks are downloadable on the site too.

Works out very cheap to do, especially as we have an army of people copying the CDs up at home :) Definately works as promotion for our nights and allows us to build up the local names, reckon it'd work for sure for a true label also.