Answer
There is no theoretical limit to the number of addresses that can be geocoded in one operation, but there are practical limits. There can be limitations on the size of the output feature class.
A personal geodatabase cannot exceed 2GB in size. A table with 6 million addresses would be limited by the maximum size of the personal geodatabase. The maximum record size is (2*1024/6) = 341 bytes. Each record in the output is likely to be significantly larger because the data will probably include a large number of fields.
By estimating the size of each record in the table, it is possible to calculate the number of records that can be geocoded in one operation in ArcGIS and written out to a single personal geodatabase.
The file geodatabase, available in ArcGIS Desktop version 9.2, can store much larger output than the personal geodatabase.
Geoprocessing operations performed on very large datasets, however, will encounter processing limitations due to available free disk space and the amount of RAM on the computer.