Your regular expressions are incorrect.
The * is a shell glob match character. For a grep RE, you need .* to match any sequence of characters.
tv*cine*edition and tv*cine*action both work because the eE and eA are consecutive. It finds zero or more of the e in cine, and then matches the next characters.
It fails for NationalGeographicWild because the ional and graphic are not matched by the * -- they need .*.