Je hebt het hier over concurrent database users? Of het aantal bezoekers op jouw website? Dat zijn twee totáál verschillende dingen.
MySQL kan in elk geval niet uit de voeten met "veel" concurrent users, vanaf 10 users gaat het al hard bergafwaarts met de performance. Sinds 5.1.x gaat het beter, maar die gebruik je dus niet.
2) Bedoel je dit op cpu niveau, dat kan ik namelijk in directadmin wel bekijken.
Wanneer er behalve de database nog andere dingen draaien, dan kunnen deze zaken elkaar in de web zitten. Zo kan bv. een mailserver of webserver alle I/O opeisen en staat de database te wachten tot de schijven weer beschikbaar zijn. Jouw database op een eigen server zetten, zou dan al een oplossing kunnen zijn.
3) We hebben de query's geoptimaliseerd, alleen is het voor mij lastig inschatten wat er nog meer kan. Hoe zou ik dit moeten vast stellen dan?
Je hebt de queries geoptimaliseerd, maar de databaseserver zelf ook? Door het juiste filesystem te kiezen, gaat de database zich al anders (beter?) gedragen, door betere geheugenconfiguraties kan het ook al beter gaan, etc. etc. etc.
4) Ik dacht dat replicatie sneller is/was dan 1 bak met betere hardware, omdat het dan niet via 1 server loopt(maar dit zal wel te kort door de bocht zijn

)
Wanneer jouw database langzaam is, zal de replica ook langzaam zijn. Die staat te wachten op data vanaf de master. Daarnaast wordt beheer een kostbare zaak, er kan nog veel meer fout gaan. En MySQL kent de nodige bugs en rottigheden met replicatie, dat is niet über betrouwbaar.
5)
Intel(R) Xeon(R) CPU E5504 @ 2.00GHz
Total Memory 16623852 kB
Free Memory 8196436 kB
MySQL 5.0.67
Php 5.2.12
Flink wat RAM, heb je jouw database daarop geconfigureerd? Zo niet, dan verklaart dat direct waarom je nog zoveel RAM vrij hebt: De database mag dit dan blijkbaar niet gebruiken.
Jouw MySQL-installatie loopt ernstig achter, deze wordt niet eens meer ondersteund. Ga upgraden naar de laatste 5.1-release, die wordt in elk geval nog tot eind dit jaar ondersteund. Daarna is het ook over en sluiten, maar dan ben je nu tenminste weer even up to date.
6) Dit lijkt mij liever een stap die ik als laatste zou zetten. Ook omdat we een aantal webshops(vele malen kleiner) op shared hosting hebben draaien, en hier is postgre niet op mogelijk
Snap ik, dit is wat ingrijpender. Maar het levert wel de grootste performance winst op. Wij draaien tot 500 concurrent users op soortgelijke hardware (met RAID 10, 4 schijven) en de database is vooral druk met niks doen. Ja, de DB verwerkt een 1500 queries per seconde, maar dat komt toch vrijwel allemaal uit RAM (de recente data is de data waarmee wordt gewerkt, dat past in RAM). Betreft OLTP, dus continue verwerking en geen website waar gebruikers tussendoor ook nog eens wat tekst moeten lezen.
1) Ga een betere versie van MySQL installeren
2) Ga een betere configuratie opzetten
3) Ga kijken wat nu het echte probleem is
4) Ga de database op zijn eigen server neerzetten
5) Hou in je achterhoofd dat MySQL niet goed schaalt en dat een migratie naar bv. PostgreSQL een optie is. MySQL heeft na 31-12-2010
geen active support meer, dat kan ook een probleem worden.
Maar replicatie, daar zou ik voorlopig nog even niet aan beginnen. Wat je nu voorspiegelt, moet makkelijk op jouw huidige server kunnen performen.