I believe the ext/mysql is deprecated, not the function names. Mysqlnd is a drop in replacement and unencumbered by the copyleft license issues that plague the original extension.
The mysql_* function API is part of ext/mysql and is deprecated — mysqlnd is a lower level library that basically replaces libmysqlclient in the stack (and is used from PDO and mysqli as well).
I'd be interested in a cite on the licensing issues, incidentally; I'm not aware of anything. (There _is_ an issue with the JSON extension at present, though, so it's not impossible.)