Understand your predicament, and will attempt to help.
1. Coffee beans are decaffeinated at the green stage.
A couple of processes are used, but by far the most popular is the swiss water process,
(which I believe is mostly done in Canada).
All water process decaff is clearly labeled as such.
Process involves heating the beans in water,
extracting the oils and caffeine,
passing the flavoured water through a separate process to remove the caffeine,
(which subsequently finds its way into various cola drinks),
passing the water back over the original beans where oils are re-absorbed.
The beans will have a characteristic brown colour afterwoods.
2. That depends on the individual, taste is something that has many factors that affect it.
Personally I have made some terrific lo-caff blends at times,
and you would be hard pressed to know it had decaff in it, if making a milk based drink.
Other times I have been able to taste a slight washed or almost buttery taste if that makes any sense. However if the trade-off is being able to sleep, then some slight different taste is not necessarily bad.
I have never tried any of the other process beans, some of the other chemical methods may leave other residual tastes that would be unpleasant (it is possible that is what you remember).
3. The process is very effective, and decaff has effectively all the caffeine removed,
there is such a small fraction of % left that it is not going to have any effect.
Correlation between taste and caffeine,....yes, caffeine tastes AWFULL, its total yuckness.
Try the exercise of pouring a shot, with three small cups/glasses prepared, collect the first third of the shot in first glass, the middle third in second glass, and put third glass under after the blonding begins and collect only the blond stuff.......then taste each one.
The blond stuff has negligible flavour oils and plenty of caffeine......
In summary I think it is best to say the caffeine doesnt do much to help the flavour of the caffee, however the process of removing the caffeine can affect the flavour of the decaff beans slightly.
4. Most would recommend trying water process decaff. A good one to start with is Columbian, which can be very nice with a slight caramel note, and is also good to blend with other beans to make lo-caff blends.
If you roast your own you will have opportunity to try various offerings that Andy finds. In the past year we have had some great decaff Yirgacheff, Columbian, Guatemala, and most recently Mocha/Java which I think is quite good.
Apart from that, see what the sponsors have.
Hope this is of some help.