Are there different types of melamine resin?
Certainly the are many different types of melamine resin.  

Is there a way to make a melamine resin without using formaldehyde?

Yes, a different aldehyde could be used such as acetylaldehyde.  Glucose, benzaldehyde, acrolein and other alternatives to formaldehyde have been studied also (see page 33 of Polymer Synthesis by  Sandler et al.). 

Is there another way to make an abrasive foam sponge out of melamine resin that is not formaldehyde-melamine-sodium bisulfite copolymer?

Good sources of information about formaldehyde-melamine-sodium bisulfite copolymer and possible alternatives are the patent Resilient foam based on a melamine-formaldehyde condensate and related patents.

First the introductory portion of the patent explains:


  It is true that foams based on melamine-formaldehyde condensates have been described in various patent publications, but they have not hitherto been employed industrially for heat or sound insulation in the construction industry. They are produced by stirring air into an aqueous melamine resin solution which contains an emulsifier and a curing agent. Such as described, for example, in German Pat. No. 870,027, have the serious disadvantage that they are very hard and brittle, and easily break or crumble when handled. It is alleged in French Pat. No. 1,073,642 that melamine resin foams can be produced by heating a resin powder in a mold under reduced pressure. This process, however, does not give useful resilient foams. U.S. Pat. No. 3,093,600 describes melamine resin foams which are said to have improved resilience and resistance to crazing as a result of the incorporation of triols, e.g. trimethylolpropane. However, it has been found that the resilience, and especially the recovery after compression, of such foams is inadequate for many applications.


Then in describing what is considered new about the invention, many different alternatives are included. Such as adding aldehydes other than formaldehyde, urea, and many other substances.