Site de encurtamento de URL

Acho que você está no caminho certo.

Uma coisa que eu não faria como você disse, porém, é sobre esta parte:

Eu não acho que criaria um Apache RewriteRule, nem usaria mod_rewrite .

Ao receber um URL curto, como short.com/MYID , Id seria:

descriptografar a parte "MYID" para o número de identificação no banco de dados
busque o URL do banco de dados
basta redirecionar para esse URL de algum código de servidor (como PHP, usando o header função)

Um pouco assim eu acho:

// fetch $urlFull from DB (corresponding to the MYID received in GET)
header('HTTP/1.x 301 Moved Permanently');
header('Location: ' . $urlFull);
die;

(editar) Se por mod_rewrite você quis dizer "transforme short.com/MYID para short.com/id=MYID ", ah, sim, neste caso, claro!

Estou usando algo assim em um dos meus sites, btw:

RewriteEngine on
RewriteCond %{REQUEST_URI}  !^/index.php
RewriteRule ^(.*)$ /index.php?hash=$1   [L]

Espero ter ajudado :-)