Ok so this was a bit of a D'oh moment. VSOnline wasn't running my tests because Specflow was building NUnit test. Changing it to build MSTest tests meant that the generated files containing the tests had the correct attributes and VSOnline recognized them and so happily built and ran them.
And using the LocalDb during the tests was fine as well, all worked like a dream.