Space in value part of RewriteMap
I've actually realized what the answer was when writing the question (classic case of rubber duck debugging).
Just add the NE flag in the RewriteRule that actually uses the rewrite map's output, somewhere along these lines:
# Define the RewriteMap
RewriteMap redirect_map "txt:redirect_map.txt"
# Look up the requested URI in the redirect map. If the result is not empty...
RewriteCond ${redirect_map:%{REQUEST_URI}} ^(.+)$
# ...then use the mapped value for the redirect, without percent-encoding it
RewriteRule . %1 [R=301,L,NE]