I thought that might be the reason, but it still is causing performance issues. Every row in the table has to go through both functions before any filtering can be applied.

How is the HTML encoded data used? You might even be better off storing a second decoded column then decode the parameter passed in to compare against the decoded column. I think this would allow for better use of any indexes.