Redirect vs Rewrite

A while ago, when my website moved to a new provider, I've had to
change all .html extensions to .shtml, otherwise the SSI wouldn't get
parsed. Now I've been trying to find a means of telling indexing
robots that the file foo.html has been permanently moved to foo.shtml.
I found two solutions:

1) In .htacces, write a line
Redirect permanent /foo.html http://www.domain.nl/foo.shtml
for each and every file on the website.

2) In .htacces, use a RewriteRule to change a request for foo.html to
foo.shtml:
# parse out basename, but remember the fact
RewriteRule ^(.*)\.html$ $1 [C,E=WasHTML:yes]
# rewrite to document.phtml if exists
RewriteCond %{REQUEST_FILENAME}.shtml -f
RewriteRule ^(.*)$ $1.shtml [S=1]
# else reverse the previous basename cutout
RewriteCond %{ENV:WasHTML} ^yes$
RewriteRule ^(.*)$ $1.html

If I use 1), a robot will be told (via a code 301) that it should
update its data. If I use 2), a robot (or any other user) will not
notice the change, and my pages will keep getting referred to as
foo.html. Is this correct, or am I mistaken here?

Is there a way to use wildcards in a Redirect line, something like
Redirect permanent /*.html http://www.domain.nl/*.shtml
?

Or should I just use the RewriteRule, and not worry about how my files
are listed, because the URI http://www.domain.nl/foo.html will also
point to the correct file?

Thanks in advance for your advice.

Best regards,
Garmt.