The feature code for Montgomery is PPLA, not PPL. Birmingham is PPLA2. You can add them by specifying featureCode more than once, with each feature code you're looking for. Keep in mind that your search is being truncated to the first 100 results.
It's not ordering them by population; the top result after Montgomery and Birmingham is Bessemer, AL (pop 27,456); the next result is Hoover, AL (pop 81,619). You're limiting your search to the first 100 out of 5386 rows (specified in the totalResultsCount tag in the header).Birmingham and Montgomery are probably in the results that are not being returned. The search function doesn't seem to have an ORDER BY equivalent. By the way, the default value for maxRows seems to be 100, so just removing it won't give you the results you're looking for. Setting it to 5386 tells you maxRows is too large. You may need to use a combination of maxRows and startRow to page your results and get a full set.
Another option would be to replace featureCode=PPL with featureCode=PPLA&featureCode=PPLA . This returns just 66 results, but drops cities that aren't county seats. Depends on what you're trying to do.
Good luck! By the way, the documentation I used for the search function is at http://www.geonames.org/export/geonames-search.html