Goldmund, "Kindest regards" is more acceptable than "Fondly" and could be used between two people with a working relationship. For instance If I had been to your home and met your family, or if I had been out for a game of golf with you. "Regards and best wishes" would probably be more appropriate. "Kindest regards." I would probably save for someone in hospital, or an elderly person. It suggests caring beyond just sending your regards.
"With regards" is fairly formal, viz "Give My Regards To Broadway." No, I would not be offended if someone ended their letter with "Regards." Regard, has several meanings. All serious and respectful. "Fondly" on the other hand has a sexual connotation, especially in England.
Fondle: Caress, to touch or stroke lovingly. (According to the OED).
Fondly: 1) Affectionate, loving. 2) Over affectionate, doting.
Affectionate: Loving, showing affection. (denoting emotion)
None of these should be used in a business letter.