Actually the limit has been increased to 5000 stars some time ago. Although I've been able to launch a game with 5000 stars, I've never played more than just a few turns on such a map - turn times are too long even in the beginning. I
did play 500 stars / 20 AI games however. That worked quite well on a two year old MBP. I got well beyond turn 200 on one of them before the game started to lag.
As far as my experiences go, the hardware seems to be the primary limiting factor. So, assuming you have limitless RAM and CPU power, go ahead and give a map with 5000 stars a shot.

Seriously, if you want to know how hard the software can be pushed, the only way to find out is to try. I don't think that anyone has been doing extensive stress testing with current releases.
As to the question, how many AIs to use on larger maps, that depends on what kind of game you want. Of course on large maps more AIs are better (playing on a 500 stars map against only one AI opponent is probably quite boring), but aside from that it mostly depends if you want to meet your opponents as soon as possible (in this case you need more AIs) or if you prefer a longer, undisturbed build-up phase for the players at the beginning of the game (in this case you need less AIs).