Well… if your POIs are stored as separate posts then the posts will get crawled like any other post.
If your POIs are all located on a single map, then they’ll be output as javascript which, I think, is usually ignored.
If you’re doing an index site – say a local directory of restaurants – then I strongly recommend you an individual post for each POI. For example, create a post for each restaurant (preferably using a custom post type ‘restaurant’). In each post, insert a map in each post with just that post’s location. Then use a mashup to display the posts together on a single map.
By using separate posts you can take advantage of all of the WordPress post features: categories, tags, a rich text editor – and SEO.