Sim, o verbo "começar" tem de ter a preposição "a" em relação a qualquer verbo no infinitivo (ir, falar, fazer, etc.). É uma questão idiomática análoga ao "ought to" do inglês. Devemos, no entanto, ter presente os seguintes aspectos:
1) Há que distinguir a construção "Começar a fazer" de "Estar a fazer".
"Estar a fazer" e "Estar fazendo" são praticamente sinônimos e "a+ infinitivo" é só uma construção que é alternativa ao gerúndio em muitos casos e é apelidado de infinitivo gerundivo.
Já o verbo começar é um verbo que pede naturalmente a preposição "a" e não pode ser substituído pelo gerúndio sem mudar o significado substancialmente.
Eu comecei a fazer... = I began to make...
Eu comecei fazendo... = I began it (by) making...
2) Há também que distinguir esta construção "Começar a fazer" de "Atrever-se a fazer".
Uma pessoa diz "Eu comecei (com) isto" mas já diz "Eu atrevi-me a isto". No segundo caso a preposição "a" é evidente, pois se trata de uma regência universal. É um caso análogo ao de "Gostar de isto" e "Gostar de fazer..."
3) Esta regência do verbo começar é de índole diferente, só acontece para introduzir um infinitvo, e por isso a pergunta está muito bem feita... Parabéns!
Um caso análogo é o do verbo terminar, só que agora é com a preposição "de"
Dizemos "Eu terminei (com) isto" mas já "Eu termimei de fazer..."
Este tipo de verbos são chamados de verbos auxiliares (que podem ter uma preposição ou não) enquanto verbos como "atrever-se", dependendo da interação com o verbo principal, podem ser considerados meros verbos em que simplesmente o infinitivo está a substantivar a oração que passa a tomar o lugar de um substantivo comum ou pronome...