O MySQL 5.0 não está disponível para nada após o Ubuntu 8.04 (hardy). 8.04 Server Edition ainda é suportado por um par de anos, então isso pode ser uma opção para você.
Aqui estão os pacotes oficiais por versão para o 5.0:
$ rmadison mysql-server-5.0
mysql-server-5.0 | 5.0.21-3ubuntu1 | dapper | amd64, i386, powerpc
mysql-server-5.0 | 5.0.22-0ubuntu6.06.15 | dapper-security | amd64, i386, powerpc
mysql-server-5.0 | 5.0.22-0ubuntu6.06.15 | dapper-updates | amd64, i386, powerpc
mysql-server-5.0 | 5.0.51a-3ubuntu5 | hardy | amd64, i386
mysql-server-5.0 | 5.0.51a-3ubuntu5.8 | hardy-security | amd64, i386
mysql-server-5.0 | 5.0.51a-3ubuntu5.8 | hardy-updates | amd64, i386
mysql-server-5.0 | 5.1.30really5.0.83-0ubuntu3 | karmic/universe | amd64, i386