あの後、さくっと解決しました！
あの「全てutf8で統一した」blog記事のまま設定したのも問題だったようです。

以下、全行程をまとめます。

まず前準備、4.1のmysqldumpで文字化けしてしまったダンプファイルを
1.秀丸でUTF8として強制的に開く（警告が出ても無視）
2.秀丸で名前をつけて保存で「欧文」を選択して保存
3.再度開くと元のDBの文字コードで開けるので、DEFAULT CHARSET=の部分を
　本来希望するCHARSETに書き換える

今回、ダンプファイルdb_sjis.dumpは、文字コードShift_JISで保存しておいて
DEFAULT CHARSET=sjisに書き換え済み。

my.cnfはきちんとサーバクライアント間で文字コード変換されるように
（※DBにはSJIS保存で、コマンド操作する端末画面表示はEUCという設定）
[mysqld]
default-character-set=sjis ←これは運用ポリシーに合わせて設定
# skip-character-set-client-handshake ←変換したいのでこれは指定しない
[mysql]
default-character-set=ujis  ←mysqlコマンドを実行するシェル画面はEUCなので。

この状態でmysqlコマンド画面では
> show variables like "char%";
+--------------------------+-----------------------------------------+
| Variable_name            | Value                                   |
+--------------------------+-----------------------------------------+
| character_set_client     | ujis                                    |
| character_set_connection | ujis                                    |
| character_set_database   | sjis                                    |
| character_set_results    | ujis                                    |
| character_set_server     | sjis                                    |
| character_set_system     | utf8                                    |
| character_sets_dir       | /usr/local/mysql4/share/mysql/charsets/ |
+--------------------------+-----------------------------------------+
この状態で、画面はujisで処理されるので、手で日本語データをinsertすると
きちんと日本語が入り、selectで文字化けせず表示されます。

いよいよダンプデータの投入。

> set NAMES sjis; を実行してから
> source /home/test/db_sjis.dump とやりましたが、これでは失敗
どうも、set NAMESはsourceコマンドの中までは影響してくれないようです。

db_sjis.dump ファイルの先頭のSQL文の直前にset NAMES sjis; を1行書いて
から、再度sourceコマンドを実行したら成功しました。

PHPスクリプトをinternal_encoding=SJISにしても、internal_encoding=EUC
にしても、どちらでもMySQL上の日本語データが、きちんとPHPの内部コードに
変換されて、日本語データが読み出されました。

以上！大成功！！