Until Office 2007, Excel has a maximum of 65,000 rows. Office 2007 bumped that up to a max of 1 million rows, which is nicer of course; but I'm curious -- why is there a limit at all? Obviously, performance will slow down exponetially as you increase the spreadsheet size; but it shouldn't be very hard to have Excel optimize for that by starting with a small sheet and dynamically "re-sizing" it only as needed. Given how much work it must have been to increase the limit from 65K to 1 million, why didn't they go all the way so it's limited only by the amount of available memory and disk space?
(updated because of error... A suggestion to everyone: don't post on SO before you are fully awake)
Probably because of optimizations. Excel 2007 can have a maximum of 16 384 columns and 1 048 576 rows. Strange numbers?
14 bits = 16 384, 20 bits = 1 048 576
14 + 20 = 34 bits = more than one 32 bit register can hold.
But they also need to store the format of the cell (text, number etc) and formatting (colors, borders etc). Assuming they use two 32-bit words (64 bit) they use 34 bits for the cell number and have 30 bits for other things.
Why is that important? In memory they don't need to allocate all the memory needed for the whole spreadsheet but only the memory necessary for your data, and every data is tagged with in what cell it is supposed to be in.
Update 2016:
Found a link to Microsoft's specification for Excel 2013 & 2016