How do you go from insights to formal solutions?
Transforming intuition into formal argument is difficult, and the degree to which it is viewed as necessary is sociological, and varies by community. In general, arguments tend to be less formal in AI conferences, reasonably formal in the "Theory A" community, and extremely formal (i.e. machine verifiable) in parts of the programming languages "Theory B" community. 

Probably the best way to develop this skill is to take rigorous courses that require formal argument on problem sets. You can also just read papers in the community that you would like to publish in, but you have to make sure to actually read the arguments carefully for this to be helpful. i.e. it is easy to read a paper and feel that you understand it, but be unable to reproduce key parts of the argument. A good way to do this is to plan to actually present the paper to a group of friends. If you actually have to present the arguments on a board and answer questions, you will be able to force yourself to really understand. 

Do this a few times and you should be able to construct formal arguments of your own.