リンク

function GetHatenaKeywordUrl($keyword) {
	$r = '';
	for($j=0; $j<mb_strlen($keyword); $j++) {
		$x = mb_substr($keyword, $j, 1);
		if(strlen($x)==1) {
			$r .= $x;
		} else {
			$r .= strtolower(urlencode(mb_convert_encoding($x,'EUC-JP',mb_internal_encoding())));
		}
	}
	return 'http://d.hatena.ne.jp/keyword/'.$r;
}

ダサァ。関数の名前じゃなくて strlen() とか。
いろいろ試してると、preg_ で UTF-8 として処理するオプションをつけると [^\S] がいわゆる全角文字だけにマッチしたので試す。

function GetHatenaKeywordUrl3($keyword) {
	if(mb_internal_encoding()!='UTF-8') {
		$keyword = mb_convert_encoding($keyword,'UTF-8',mb_internal_encoding());
	}
	$r = preg_replace_callback('/([^\S]+)/u', 'GetHatenaKeywordUrl3cb', $keyword);
	return 'http://d.hatena.ne.jp/keyword/'.$r;
}
function GetHatenaKeywordUrl3cb($a) {
	return strtolower(urlencode(
		mb_convert_encoding($a[0],'EUC-JP','UTF-8')
		));
}

処理時間が1/5になったけど微妙。