Thermally annealed soft carbon and hard carbon samples were investigated by a variety of methods. The ordering of the carbon matrix with increasing heat-treatment temperature was followed by X-ray diffraction (XRD), transmission electron microscopy (TEM) and Raman spectroscopy. The state of Li ions that can be incorporated in the evolved carbon structures was probed using 7Li NMR spectra and by 7Li NMR spin-relaxation that report the different aspects of order and disorder at the available sites. These latter observables were recorded at different temperatures that permitted separating the various structural and dynamic features (including Li ion diffusion) influencing them. Both the initial structures and their respective structural evolution were shown to be complex. While all observations pointed to an increasing order and an increasing size of domains upon increasing heat-treatment temperature, the change in Li capacity is either non-monotonic (soft carbon) or increasingly diverging from the graphite value (hard carbon). We propose that these, apparently, contradictory trends are partly caused by kinetic limitations. Heat treatment at 2500 degrees C turned the dominating fraction of the soft carbon to essentially graphite with regard to both atomic and electronic structures and long range order, yet also created a minor fraction with a disordered structure that is responsible for the total capacity exceeding that for graphite. Untreated hard carbon permitted metallic clusters, but heat treatment eliminated the necessary sites and/or access to those.