Воможно ли к существующей оперативке 2хDIMM 512 Mb DDR2 533Mhz добавить 1 Gb оперативки DDR2 800MHz ?

Если слотов хватает, то можно.
В большинстве случаев заработает.
Иногда бывают глукю с несовместимостью памяти

И слотов хватает, и материнская плата поддерживает обе частоты, просто в одном компьютерном магазине сказали, что у оперативки должна быть одна частота.

просто когда оператива разной частоты все планки будут работать на наименьшей частоте. в вашем случае это 533.

и потому в вашем случае я бы попробовал сначала поставить одну новую планку и посмотреть, что из этого выйдет. А пока продайте старые и подкопите на ещё одну на гиг =)

Вот это однозначно самое лучшее решение.
Когда память одномастная, она работает в дуале.