Thanks everyone! What I have now is functional at least; it's good to know that the performance can be improved down the line.
P.S. Does anyone have much interest in a c# implementation? I started this mostly to educate myself, but I'm making more progress than I was expecting.
Hey pmlyon, I am interested in a C# implementation of the ECDSA based message sign & verify in Bitcoin-QT.. See this thread
https://bitcointalk.org/index.php?topic=297097.0. Hhave you had a go at implementing that in your project yet?