Like EQ said, Your lowpoly mesh that will be using the normal map in the end needs to have the same normals as the lowpoly mesh used when baking. In other words, you can't just "soften" the edges on the lowpoly using the normal map and expect it to work. You need to re-bake with a lowpoly version with softened edges as…
You softened the edges of the lowpoly target and rebaked. Then applied the newly baked to a lowpoly version with the same softened edges? Or did you just soften the edges on the model which is going to be using the normal map? Because when you say "I tried softening all my edges in Maya..." sounds to me like you are just…
are you re-exporting a lowpoly mesh from mudbox? or are you just using the lowpoly that you made in maya? If you're still using the maya model then that is a problem. When you sculpt in mudbox it moves the base mesh around and the one before mudbox won't fit the hipoly properly anymore.
Whaaaaaa? No, really i have no idea why someone would ever tell you this. You generally want have the normals on your lowpoly mesh averages(ie: soften edges) and only use hard edges when you run into smoothing errors. Theres tons of into documenting normal maps and how they work if you search or browse the stickied threads…