Some years ago, when I hacked on a TDB backend for Evolution Data Server (EDS), I also wrote something about writing some command line tools for accessing my contacts and so on. I’ve finally gotten my act together and wrote the necessary glue to have addres completion between Gnus and EDS. It’s nowhere as feature-complete as BBDB is, but it allows you to complete addresses, at least. Get it from git (gitweb). I’ll hopefully expand it a little bit and cut a release fairly soon.