全文索引の使用を検討し、FREETEXT と CONTAINS の機能を使用して検索を行うことができます。
編集:全文索引検索の改良を引き続き検討しますが、別の回答から続けるために、これは REPLACE を使用するオプションです。
SELECT
Artist,
Title
FROM
Songs
WHERE
REPLACE(REPLACE(REPLACE(Artist, '#',''), '*', ''), '"', '') LIKE '%Keywords%'