Search Function / Listing Products

I’m looking to add 2 search criteria for my products (Size and colour). However, i can’t seem to get things working correctly. I’ve tried adding them as custom fields with drop down boxes in the search options and tick boxes in the listing screen to add multiple variations for that product. This visually is perfect however the search doesn’t pick up the variations.

I’ve now been told that this does not work and to use taxonomy and can only have multiple check boxes. This actually does work functionally but now the user can select multiple sizes etc when searching which i would not want them to do. This also does not work for me as when listing a product by a user as it’s a taxonomy they only have a choice to select one variation in a drop down box so means they would have to create a separate listing for each variation.

Any suggestions or tips on how you would set up having search criteria would be much appreciated.

Thanks

Mark