He's de-registered his phone number from iMessage and I've reset and restarted iMessage on my phone (iPhone 8). But I still can't send him messages.
Anyone know of a fix?
You can ask your friend to Deregister iMessage. It can be done both on the iPhone or if they no longer have access to the iPhone, on the Web.
See the linked Apple Support article to learn more:
Since your friend has already moved to an Android phone, it would be easier for them to deregister online. Here's the webpage that can be used to deregister iMessage: