Given that WiFi packets should be encrypted if WPA2 is used, why is it that a deauth attack can be successful? Shouldn't the machine know that the message is illegitimate due to the fact that it would not be encrypted, having come from a fake source?
The use of encryption in 802.11 is limited to data payloads only. Encryption does not apply to the 802.11 frame headers, and cannot do so as key elements of 802.11 headers are necessary for normal operations of 802.11 traffic.
Since 802.11 management frames largely work by setting information in the headers, management frames are not encrypted and as such are easily spoofed.
To prevent deauthentication/disaccotiation attacks, the IEEE implemented the 802.11w amendment to 802.11. This provides a mechanism to help prevent the spoofing of management frames, but both client and infrastructure need to support it (and have it enabled) for it to function. You can find a bit more information on 802.11w in my answer here if you wanted to learn more.
That's one of the major problems with the 802.11i standard. Deauthentication frames, as well as all other 802.11 management frames, are not encrypted. As you observed, anyone can craft deauthentication frames or any other management frame.
802.11w was introduced to fix this issue, allowing for protected management frames (PMF). If a device requires PMF but receives an unsolicited management frame (e.g. deauthentication), it can ignore it. However, it is not widely adopted and does not completely solve the problem*.
*: 802.11w protects against some specific types of attacks. There are many other layer 2 abuses of 802.11 that it does not protect against, either because they were not considered, or it is not trivially possible to prevent them while keeping the protocol intact. There are a number of articles and research papers out there that go over such issues.