If you create a new entry on the Palm and fill out both the Name and Company fields, MaxLink will create the record in Maximizer as an Individual with the "Company" field filled out. It won't actually create a Company/Contact relationship in Maximizer like you're expecting. MaxLink doesn't work that way.
This is a problem because of the way the Palm stores data versus how Maximizer stores data. Palm is a "flat" system and Maximizer is a "parent/child" system. On the Palm, there is no relationship between the records. In Maximizer, obviously, there is a relationship between a company (or an individual) and its contacts. When you attempt to tie these two structures together, you're going to have some issues like this.
To get Palm to mimic the "parent/child" relationship of Maximizer, you have to use a special code that ties the records together. This should be covered in the MaxLink User Guide which is available from their site.
When you add records in Maximizer, these keys are automatically created to preserve the "parent/child" relationship on the Palm. When you add records on the Palm and wish to mimic this relationship between two records, you have to manually tie the Palm records together using the keys.
Again, consult the user guide for more specific details.