I don't know why having index.php in the href in an a tag would ever matter, aside from using since you can just edit the HTML.
This is starting to sound a bit circular :) If something is in the href, then that is what the user's browser will request when they click on the link. And what the search engine will put on its shopping list.
Editing the html-- or the php that generates the html-- to get rid of unwanted links is an essential first step. But it doesn't retroactively change existing bookmarks, browser histories or search-engine lists. That's where you need the redirect.
If google has requested the wrong url even once, you will need a redirect forever. Or be content with google getting 404s forever. You can get rid of them faster with a 410, but it doesn't work on all search engines.