Q>Как получить список установленных программ. И как узнать насколько часто запускалась та или иная программа из данного списка.

Q>Интересует реализация с помощью Visual C++ с использованием только средств WinAPI.

Есть ключи в реестре, где программы о своей установке успешной сообщают. Тут поиск поможет.

Для отслеживания запуска программ вариантов есть :
— свои хуки,
— смотрите PSAPI в MSDN — это поможет получить список запущенных программ,
— еще есть на www.codeguru.com и www.codeproject.com примеры в эту степь