A good tip for those who haven't already tried it.

I actually used a bit of simple green and some just boiling water. You have to fill the bottles with hot tap water to get them to sink but if you leave them sit for just a hour or more the labels slide right off and if it way really heavy glue you may need a quick wipe with a sponge.

Here is another tip. If you make your own labels apply them with milk.
Just take your label and a wide paint brush. Dip the brush in milk and lightly brush it onto the back of the labels and put them on your bottles. They hold well and are a piece of cake to remove.