After looking at some seo companies, I notice that their index page focuses on the keyword "SEO", and other pages of their website also have SEO in them, but they don't link back to their main index page with the anchor text "SEO".

I'm sure this means they have a keyword cannibalisation problem, or are the search engines smarter than I think? Can the search engines work this out without the user needing to link back to every single page with the keyword to try and avoid this problem?

I'm not sure what the "problem" is here.

It does help a page rank better for a given keyword if inbound link text includes that keyword. However, this is not the only factor, just one of many. So, a page can rank just fine if it does not have backlinks with that keyword, but it should rank a little higher with such links (especially with external links using that keyword).

You do need to be careful about abuse here -- search engines will identify and ignore cases where link text is used excessively.

The sites you looked at may just not be using this technique, or they may have chosen to emphasize other keywords in the anchor text they are using. After all, "SEO" is an intensely competitive keyword, and the sites you looked at may conciously be targeting other terms through their anchor text.