Welcome to WebmasterWorld Guest from 220.127.116.11
Some hosting services will rotate the MX server IP address, cycling through a dedicated group. So your MX server's IP address may change, even though your domain's IP address does not change.
Also be aware that private blacklists may have it, although there isn't much you can do about that since you have no way of knowing. Except for Yahoo etc - and they are a sod to get delisted from.
Also check that rDNS is not still set up for it (apart from your own, obviously) and get it removed. If it's an expired or pirated domain it could end up embarrassing you.
Also check that the IP has no history of sending out viruses or hosting hacked sites: there are services that return data on these.
It's not so much a question of google not accepting the IP. IPs are usually assigned to a hosting company. If it's been compromised once then it may well be again: the hosting company may be spammer/exploiter friendly or just be rubbish at maintaining data centre security. If so, you do NOT want to use them.
I suppose this comes down to researching the hosting company as much as the IP itself. :)