With the number of products mentioned, if you have multiple stores, and lots of different Catalog Price Rules, all of this multiplies the amount of data that has to be taken out of the EAV tables and put into flat tables. Depending on what type of hardware you are hosting on, you may want to consider upgrading if you are hitting high load averages, consider hosting your MySQL database in another server with more resources available.
With all that said, there are some ways not involving hardware upgrades, if you are indexing via the shell, using php shell/indexer.php without any options or simply info will give you a list of options to use, instead of using reindexall you can index each indexer separately to help identify the failing ones and not reindex indexes that have already been indexed with using reindexall.
Disable any core modules you do not need or used, RSS especially:
https://magento.stackexchange.com/questions/8746/disabling-modules-performance-improvement
Magento does not ignore simple products that are set to "Not visible" and creates URL Rewrites for them, this module excludes them from the URL Rewrite indexer:
https://github.com/molotovbliss/DnD_Magento_Patch_Index_URL
Source: http://www.dnd.fr/2012/09/magento-patch-how-to-optimize-re-index-processing-time-for-url-rewrite/
Also, it helps to keep your MySQL database as lean as possible removing any non-required data like logging, and dataflow import tables, as well as quote entries from guest customers who added something to cart and never checked out:
https://github.com/fbrnc/Aoe_QuoteCleaner
If you are on a multi-core server since PHP processes are single threaded only one CPU core is used during indexing, a free (although old) module does exist for utilizing the additional CPU cores, however you may have better results with the paid for solutions.
Free: https://github.com/AOEmedia/Aoe_Index & https://github.com/magento-hackathon/AsyncIndex
Paid: https://www.magentocommerce.com/magento-connect/fast-asynchronous-re-indexing.html
You can also use some common tools like mytop, htop, mysqltuner.pl or mysql-primer to monitor MySQL resources and get recommendations on MySQL changes (if you are able to edit my.cnf/ini) Some further details on these: https://magento.stackexchange.com/questions/13957/full-page-cache-on-ce-1-8-an-fpc-magento-module-va...
Hope this helps, cheers! 
Also, if you are curious of the internal workings and reasons why indexing is needed for Magento: http://magento.stackexchange.com/a/90121/69
Hello B00MER,
thank you for detailed post, I appreciate it very much!
It is very clear and I'm working on your suggestions.
It is a little bit difficult because I'm not programer, but what is one of the problem with slow reindex.
Firstly, your explanation about rewrites.
I noticed that we have too many SKUs with same url_key. So magento every time add random number after that url_key.
I emptied core_url_rewrite and run reindex, and for 17000 skus (only about 4000 active) I got about 200K rows in that table.
After every next reindex add new 115K rows in table.
Maybe reindex working slow because that?
I wan't to change script for product update (I'm updating it with magmi), and set url_key to be unique. So in my case now is
sku = dasd32424
description = brand-shoes
url_key = brand-shoes.
Like I said, we have more different "brand-shoes" articles, and I'm just guessing that magento add some random number after that "url_key", and every time that number is different.
So at this moment probably I need to export all SKU-s and description, and make third column "url_key" to be description+sku. It is important that link have also description.
But I don't know to make sql query to get all sku-s and description.
Also I have two different stores. 1 and 11, for our language and english.
Uh too long post, sorry
