qxfusion

Хоть это и не афишируется — но да, также зависит от того на кого регистрировали аккаунт, приложения от компаний всегда рассматривают раньше чем от физических лиц. Также если Ваше приложение использует какой-либо особый функционал API (в т.ч. и хаки) — его будут смотреть с особой тщательностью. И не забывайте что если в сторе есть очень похожее приложение от другого крупного вендора, то Ваше теоретически можен и не пройти.
P.S. и не забывайте про волшебный пункт который позволяет не принимать любое приложение без объяснения причин.

Тут явно видна просадка дисковой подсистемы — для сервера который Вы указали можно установить.

Дисковая подсистема:
(1) 2 x FusionIO ioDrive 160GB PCI-E — в режиме увеличенной производительности (доступная емкость будет уменьшена в 2 раза до 80GB) — соединив в soft RAID0 (по цене это будет где-то 2 x 2-2.5k$) (по IOPS подойдут для обоих баз)
(2) 3 x SCSI 146GB RAID5 — бэкап с FusionIO
(3) 2 x SAS 10k 300GB — для системы

Память:
увеличить размер памяти до 48GB 12x4GB

По поводу конфигурации нового сервера — то порекомендовал бы HP DL серия Gen8 исходя уже из оставшегося бюджета

В случае с OpenVZ почти никак, для остальных гипервизоров (1) ставить ядро с патчами на шифрование RAM (производительность падает в несколько раз) (2) контроль целостности системы (список процессов, диск и т.д.)

1) сделать отдельный домен под статику
2) поставить на этот домен балансир — например static.site.com -> 0.static.site.com, 1.static.site.com и т.д.
3) обновить настройку — т.к. связка nginx+php_fpm 97% случаев быстрее чем httpd+mod_php (если нету явных завязок на httpd)
4) VDS — смотря у какого хостера, у РУ как правило идет оверселл — что (1) получаете меньше % CPU (2) сеть и без Вас утилизирована до предела, а у хостов часто ставят лишь 100Mbps
P.S. от себя добавлю — переходите в облако, например у Joyent небольшой инстанц стоит недорого + возможность масштабирования на лету (правда тут тогда лучше использовать Joyent SmartOS — удобнее будет) + 10Gbps общий шаред порт (гарантированная скорость равна доле ресурсов от RAM — т.е. если Вы купили 1GB инстанц — то получите гарантировано — 10Gbps/80*1 = 125Mbps теоретической скорости сети (в реале будет до 100Mbps)) и 20TB/mo./instance премиум трафика.

Я всегда устанавливаю через снимки, далее нужно зайти через SSH на систему и обновить пакеты до актуальных. (yum, zypper, apt-get на Ваш выбор.
Исходный снимок рекомендую делать с LVM в качестве базы и с минимальным размером начального аллоцирования томов.

/swap — 8GB (130% RAM) swapfs
/boot — 64MB fat32 или ext3
/var — 16GB ReiserFS на мелкие файлы (по хорошему лучше конечно сложить в RAM)
/ramdisk — 128MB tmpfs * часто бывает нужно для обработки множества мелких файлов чтобы не забивать основную ФС
/ — 64GB BtrFS * как по мне так лучший вариант
/home — * BtrFS или XFS

возможно — можно подключить через Wireless USB — дорого, но модно :)
а если серьезно — то лучше использовать
1) роутер в качестве моста (если есть порт USB)
2) RaspPI model B (USB для диска + Ethernet под сеть) — самый бюджетный
3) самому собрать NAS (от 300$ x86, от от 125$ ARM)