We did a quick search of this database to see if there were any other records relating to your father. The only record was for the dissolution of their marriage on Aug. 24, 1973. This record is less likely to list the names of your father’s parents, but you might want to look at it.
You may also want to search for a marriage certificate for your grandparents. From your family members you know that your grandfather moved to Detroit and married there. If you are able to confirm that your grandfather’s name is Allen Gregory Bailey, you can start to search for his marriage record.
Marriage, divorce and death records in Michigan are open to the public and can be requested online or through the mail. The Michigan State Vital Records office does not have an index of its marriage records available online, so you may want to contact the office to inquire about an index lookup before ordering a record.
Another source that may be useful in finding more information about your paternal grandparents is city directories and phone books. The latest city directory available online through Ancestry.com is the 1960 City Directory of Boulder (registration required). There were several families with the Bailey name living in the area, but the directory did not show entries for Allen Gregory Bailey.
The Carnegie Library in Boulder has a collection of city directories, yearbooks and phone books that might have records of your father and grandfather. It may be useful searching the directories and phone books for 1970, the year your parents were married, to see if there are any entries for Gregory Allen Bailey and then to see if there are any other entries for those with the Bailey surname living at the same address. It’s possible that your grandmother’s first name is also listed. Before you visit, you may want to contact the library and ask about its holdings around the 1970s. If you are unable to visit, you may also ask whether the library has a lookup service available.
You also mentioned that your paternal grandfather left the reservation to join the military. Given this, your family may have moved around frequently, so military records may be another useful source of information. Your grandfather may have been old enough to serve in World War II. The website Fold3.com has some military records from that war. Although it’s a paid-subscription site, occasionally local libraries will have a subscription available for patron use.
Once you find more information about your grandfather, you can also request his military personnel file. Instructions on how to request a personnel file can be found here. More general information about finding information on World War II veterans can be found in this publication by the National Archives and Records Administration (pdf).
Search for Records of the Bailey Family in the 1932 Indian Census Rolls