Imagine you have delivery problems with Gmail due to bad past behavior (ie. sending to non-legitimate contacts, not respecting spam requests, not respecting unsubscriptions, etc...).
You might come up with the idea or be suggested that changing your sending IP will solve the problem immediately.
Well think again. Anti-spam systems are not so stupid and they are used to deal with professional spammers changing domains and IPs all the time in order to send their spam. Anti-spam systems are smart enough to recognize a new IP replacing an old one which has a bad sending reputation and allocated immediately the same reputation to the new IP!!!! This way, your new expensive fresh new IP will be immediately marked as a bad sender !! And you can repeat the process as many times as you want, you'll get the same results !
In the case of Google, who has clear and elaborated policy in this sense, if a Message ends-up in their spam folder, it really means that recipients complain about sendings. Changing IPs will be blocked anyway in a short delay.
The solution with Gmail delivering to spambox is the following, first validate their guidelines POINT by POINT :
This page also incldes troubleshooting tips and eventually lead to a contact form:
At present, this is the only known successful way to solve a Gmail delivery problem.