Memoization is a performance optimization, not a means to achieve referential transparency

memoization.py

# Memoization doesn't get you all the way there. While a memoized
# function might exhibit referential transparency *at two successive
# callsites*, your program as a whole will not exhibit that
# property. An example with destructive updates of a mutable data
# structure, an inherently effectful operation:

phonebook = {}

# assuming this function is augmented with memoization

def add_contact(name, phone):
    phonebook[name] = phone
    return phonebook

# Example #1 - a sequence of calls, the end result of *all* calls
# should be the same no matter how I order them

add_contact('Edward', '918-555-1234') # returns {'Edward': '918-555-1234'}
add_contact('Edward', '918-555-1234') # returns {'Edward': '918-555-1234'} from cache
add_contact('John',   '918-555-5678') # returns {'Edward': '918-555-1234', 'John': '918-555-5678'}

# Example #2 - swap the order, and the results of individual calls are
# completely different compared to the first example

add_contact('John',   '918-555-5678') # returns {'John': '918-555-5678'} 
add_contact('Edward', '918-555-1234') # returns {'Edward': '918-555-1234', 'John': '918-555-5678'}
add_contact('Edward', '918-555-1234') # returns {'Edward': '918-555-1234', 'John': '918-555-5678'} from cache

# Example #3 - a memoized function also can't enforce its own contract
# when the data is mutated by another source

add_contact('Edward', '918-555-1234') # returns {'Edward': '918-555-1234'}
phonebook['Edward'] = '918-555-5555'
add_contact('John',   '918-555-5678') # returns {'Edward': '918-555-5555', 'John': '918-555-5678'}

# Example #4 - most insidiously, in the presence of concurrency (even
# with correct locking, which is elided here) the behavior is
# non-deterministic.

thread.start_new_thread(lambda: phonebook['Edward'] = '918-555-5555')

add_contact('Edward', '918-555-1234') # returns {'Edward': '918-555-1234'}
add_contact('John',   '918-555-5678') # returns ???

# TLDR: Immutability is key to referential transparency.

I think what Brian was getting at was that a "dirty" implementation can behave as though referentially transparent when viewed from the outside. Your add_contact function modifies state that's external to it.