Increase the amount of segments when you create them. You can also use extrude to add faces (and verticies) or boolean to cut. Be careful with boolean, as it can really increase your polycount and may require a bit of cleanup.
Although all the methods espoused above will add vertices to any 'polygon', (plane) I do not believe it is possible to 'add' a vetex in the manner I suspect you want to do it. There is no facility in Gmax (or it's big brother 3ds Max) to randomly 'place' a vertex on the surface of an existing polygon and integrate it automatically into that polygon's parameters. Quite why this option is not available I do not know - you will have to take that up with the programmers at Autodesk.
That method will certainly be the most efficient way to get the job done, however, it involves a certain amount of work on the part of the operator, whereas there really is no reason why a simple click to locate the desired point where a new vertex is wanted on the 'plane' of the desired polygon and to have that vertex become integrated into the polygon, could not be a feature of the program.
Anyway, even doing it your way is still not a 'perfect' solution, since even though all the vertices are suitably welded together, the 'lines' or edges created by them are not, which means that where there was just one edge attached to an "original" vertex, there are now two or more where the added vertices were welded. This may cause problems for certain line functions at a later time.