Follow up ques: If parent key at m/44'/0'/0'/0 is found to be valid, shouldn't I be checking the corresponding parent key of internal chain at m/44'/0'/0'/1 before assuming its safe to use? Otherwise we would have no valid change addresses to send money to.
Each key is checked only when it is generated and wallets usually generate a bunch of them at a time, there is no need to check the ones that may be generated in the future. Keep in mind that chances of finding an invalid key is extremely small since sekp256k1 order is very close to 2
256.
If a child key was invalid you simply skip it and get the next one, meaning m/44'/0'/0'/0/0, m/44'/0'/0'/0/1, m/44'/0'/0'/0/2, m/44'/0'/0'/0/4, m/44'/0'/0'/0/5 assuming index=3 gave an invalid key.
But if the parent key (eg the key at depth 1) was invalid you should stop, that would be a very unlikely error and the seed must be changed, meaning stop if m/44'/ was invalid. At least that is what I do in my Bitcoin.Net code.