How to improve performance of this recursive function?

I think you should eliminate the recursion altogether. Instead of doing all that find and replace, you could, for example, decide upon a "normal form" of your input strings, convert them accordingly (i.e. replace those "ambiguous" characters) and do a simple

return substring in string_

Note also that you don't need to call find and replace together, the latter sufficies. If the search string isn't found, replace just won't replace anything.

Try

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import re

def danish_tolerating_search(search, content):
    search = search.lower()
    content = content.lower()

    variants = {
        u'a': u'[aæå]',
        u'o': u'[oøå]',
        u'ae': u'(?:ae|æ)',
        u'ea': u'(?:ea|æ)',
        u'aa': u'(?:aa|å)',
        u'oe': u'(?:oe|ø)',
        u'\\å': u'(?:[oå]|aa?)',
        u'\\ø': u'(?:ø|oe?)',
        u'\\æ': u'(?:æ|ae?|ea)',
    }

    search = re.escape(search)
    search = re.sub(ur'[ae]a|[ao]e?|\\[åøæ]', lambda m: variants[m.group(0)], search)
    return re.search(search, content) is not None

I did not test its performance because OP did not release any. I'll just assume the regex engine is better optimized than calling OP's s() recursively and doing lots of .find and .replace.

Here, the key letters in the search string are replaced by the possible equivalent classes in terms of regex, e.g. Ålborg becomes (?:[oå]|aa?)lb[oøå]rg. This regex should include all possible variants equivalent to Ålborg (ålbørg" or "ålbårg" or "aalborg" or "aalbørg" or "aalbårg" or "alborg" or "albørg" or "albårg" as mentioned by @101100's comment). Then the regex is simply searched against the context.

This is a classic example of a parser. Read up on things like lex and yacc, you won't need all of their functionality, but the principles still apply.

After that, use the python re module to match against the appropriate regular expressions. If you need more functionality, use the pyparsing libraries.

def danish_tolerating_search(substr, str):
'''Figure out if substr is in str, taking into account
possible deviations in writing letters æ, ø, å.
æ  <->  ae a ea
ø  <->  oe o
å  <->  aa a o
for all of these combinations replace with appropriate regex as in example
'''
substring = substring.lower().replace('aa', '[ae]{1,2}')
string = string.lower()
re.search(substring, string)